SoFunction
Updated on 2024-11-15

Python implementation of the array translation K-bit problem

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.