Блог

Напишите функцию rotate(ar[], d, n), которая поворачивает arr[] размера n на d элементов.

Вращение вышеупомянутого массива на 2 сделает массив массивом

СПОСОБ 1 (с использованием временного массива):

Input arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2, n =7
1) Store d elements in a temp array
 temp[] = [1, 2]
2) Shift rest of the arr[]
 arr[] = [3, 4, 5, 6, 7, 6, 7]
3) Store back the d elements
 arr[] = [3, 4, 5, 6, 7, 1, 2]

# function to rotate array by d elements using temp array
def rotateArray(arr, n, d):
	temp = []
	i = 0
	while (i < d):
		temp.append(arr[i])
		i = i + 1
	i = 0
	while (d < n):
		arr[i] = arr[d]
		i = i + 1
		d = d + 1
	arr[:] = arr[: i] + temp
	return arr


# Driver function to test above function
arr = [1, 2, 3, 4, 5, 6, 7]
print("Array after left rotation is: ", end=' ')
print(rotateArray(arr, len(arr), 2))

# this code is contributed by Anabhra Tyagi

Выход:

Array after left rotation is:  [3, 4, 5, 6, 7, 1, 2]

Временная сложность: O(n)
Вспомогательное пространство: O(d)

СПОСОБ 2 (Вращайте один за другим) :

leftRotate(arr[], d, n)
start
 For i = 0 to i < d
 Left rotate all elements of arr[] by one
end

Чтобы повернуть на единицу, сохраните arr[0] во временной переменной temp, переместите arr[1] в arr[0], arr[2] в arr[1] …и, наконец, temp в arr[n-1]
Возьмем тот же пример обр.[] = [1, 2, 3, 4, 5, 6, 7], d = 2
Поверните arr[] на единицу 2 раза
Мы получаем [2, 3, 4, 5, 6, 7, 1] после первой ротации и [ 3, 4, 5, 6, 7, 1, 2] после второго поворота.

#Function to left rotate arr[] of size n by d*/
def leftRotate(arr, d, n):
	for i in range(d):
		leftRotatebyOne(arr, n)

#Function to left Rotate arr[] of size n by 1*/
def leftRotatebyOne(arr, n):
	temp = arr[0]
	for i in range(n-1):
		arr[i] = arr[i+1]
	arr[n-1] = temp
		

# utility function to print an array */
def printArray(arr,size):
	for i in range(size):
		print ("%d"% arr[i],end=" ")


# Driver program to test above functions */
arr = [1, 2, 3, 4, 5, 6, 7]
leftRotate(arr, 2, 7)
printArray(arr, 7)

# This code is contributed by Shreyanshi Arun

Выход:

3 4 5 6 7 1 2 

Временная сложность : O(n * d)
Вспомогательное пространство : O(1)

МЕТОД 3 (Алгоритм жонглирования)

Это расширение метода 2. Вместо того, чтобы перемещаться по одному, разделите массив на разные наборы, где количество наборов равно GCD из n и d, и переместите элементы внутри наборов. Если GCD равен 1, как в приведенном выше примере массив в (N = 7 и D =2), то элементы будут перемещены в один набор только, нам просто не начать с Temp = arr[0] и продолжайте двигаться arr[I+d] на arr[I] и наконец, магазин темп в нужном месте. Вот пример для n =12 и d = 3. GCD равен 3

Let arr[] be {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}

a) Elements are first moved in first set – (See below diagram for this movement

          arr[] after this step --> {4 2 3 7 5 6 10 8 9 1 11 12}

b)    Then in second set.
          arr[] after this step --> {4 5 3 7 8 6 10 11 9 1 2 12}

c)    Finally in third set.
          arr[] after this step --> {4 5 6 7 8 9 10 11 12 1 2 3}

#Function to left rotate arr[] of size n by d
def leftRotate(arr, d, n):
	for i in range(gcd(d,n)):
		
		# move i-th values of blocks
		temp = arr[i]
		j = i
		while 1:
			k = j + d
			if k >= n:
				k = k - n
			if k == i:
				break
			arr[j] = arr[k]
			j = k
		arr[j] = temp

#UTILITY FUNCTIONS
#function to print an array
def printArray(arr, size):
	for i in range(size):
		print ("%d" % arr[i], end=" ")

#Function to get gcd of a and b
def gcd(a, b):
	if b == 0:
		return a;
	else:
		return gcd(b, a%b)

# Driver program to test above functions
arr = [1, 2, 3, 4, 5, 6, 7]
leftRotate(arr, 2, 7)
printArray(arr, 7)

# This code is contributed by Shreyanshi Arun

Выход:

3 4 5 6 7 1 2 

Временная сложность : O(n)
Вспомогательное пространство : O(1)

Другой подход : Использование среза списка

# Python program using the List
# slicing approach to rotate the array
def rotateList(arr,d,n):
arr[:]=arr[d:n]+arr[0:d]
return arr
# Driver function to test above function
arr = [1, 2, 3, 4, 5, 6]
print(arr)
print("Rotated list is")
print(rotateList(arr,2,len(arr)))

# this code is contributed by virusbuddah

Выход:

[1, 2, 3, 4, 5, 6]
Rotated list is
[3, 4, 5, 6, 1, 2]

Если массив нужно повернуть больше, чем на его длину, то следует выполнить мод.

Например: поверните arr[] размера n на d, где d больше n. В этом случае d%n следует вычислить и повернуть по результату после mod.