Python Array Shift by K Bits
def move(ls: list, offset): """ The sum of the original index of the element + the number of displacements (positive for right shift, negative for left shift) is solved for the remainder about the length of the array (the modulus of the array), i.e. the index of the element after displacement. The new index is then sorted in ascending order, removing the index, which is the new array after the displacement :param ls. :param offset. :return. """ mod = len(ls) ids = [[(item[0]+offset)%mod, item[1]] for item in enumerate(ls)] (key=lambda item: item[0]) return [item[1] for item in ids] def move2(ls: list, offset): """ Segmented inversion, bounded by the number of displacements (to modulo the remainder), inverts the two subarrays separately, and then inverts them as a whole :param ls. :param offset. :return. """ mod = len(ls) offset = offset % mod tail = list(reversed(ls[mod-offset:])) head = list(reversed(ls[:mod-offset])) return list(reversed(head+tail)) if __name__ == '__main__': nums = [8, 9, 10, 11] print(move(nums, 1)) print(move2(nums, 1)) print(move(nums, -1)) print(move2(nums, -1)) """ [11, 8, 9, 10] [11, 8, 9, 10] [9, 10, 11, 8] [9, 10, 11, 8] """
Python circular shifting of arrays
request
A cyclic right shift of K bits for an array containing N elements requires a time complexity of O(N) and allows the use of only two additional variables.
analyze
Method 1: Brute force method
Requirements for the array elements to cycle right shift K bits, only need to each time the elements of the array right shift one, cycle K times can be. Such as the original array for abcd1234, right shift 4 specific move process for abcd1234 -- >4abcd123 -- >34abcd12 -- >1234abcd.
Method 2: Flip method
Directly on the example, for the array sequence A = [123456], how to realize the loop right shift 2 bits function? Divide the array A into two parts A[0,N-K-1] and A[N-K,N-1], flip these two parts separately, then put them together and flip them again as follows:
- ①Flip 1234:123456-->432156
- ②Flip 56:432156-->432165
- ③Flip 432165:432165-->561234
code implementation
# Method I # -*- coding:utf-8 -*- def rightShift(arr,k): if arr == None: print("The parameters are not legal!") return lens = len(arr) k %= lens #Because K is not necessarily less than N and may be greater than or equal to N, when K ≥ N, shifting right by K-N has the same effect as shifting right by K bits while k != 0: # Shift right by k bits tmp = arr[lens-1] The last element of the #array is placed in a temporary variable i = lens-1 while i > 0: arr[i] = arr[i-1] # All elements moved back i -= 1 arr[0] = tmp # The first element is the value of the initial last element k -= 1 if __name__ == "__main__": k = 4 arr = ['a','b','c','d','1','2','3','4'] rightShift(arr,k) i = 0 while i < len(arr): print(arr[i],end="") i += 1
Run results:
1234abcd
# Method II def reverse(arr,start,end): while start<end: temp = arr[start] arr[start] = arr[end] arr[end] = temp start += 1 end -= 1 def rightShift(arr,k): if arr == None: print("The parameters are not legal!") return lens = len(arr) k %= lens reverse(arr,0,lens-k-1) reverse(arr,lens-k,lens-1) reverse(arr,0,lens-1) if __name__ == "__main__": k = 4 arr = ['a','b','c','d','1','2','3','4'] rightShift(arr,k) i = 0 while i < len(arr): print(arr[i],end="") i += 1
running result
1234abcd
performance analysis
The time complexity of method 1 is O(N) for each move, so moving K times, the total time complexity is O(K*N), 0<K<N and the time complexity does not satisfy O(N).
Method 2 has a time complexity of O(N) and uses only one auxiliary storage space to complete the flip operation.
summarize
The above is a personal experience, I hope it can give you a reference, and I hope you can support me more.