Как повернуть целочисленный массив на i раз, используя функцию swap только в линейном времени.
Алгоритм повернуть массив в линейном времени
Ответ 1
Вы можете сделать это в линейном времени с помощью вспомогательного элемента reverse().
// rotate array of size=size, by n positions
void rotate(int array[], int size, int n)
{
// reverse array[0...size-1]
reverse(array, 0, size-1);
// reverse A[0...n-1]
reverse(array, 0, n-1);
// reverse A[n...size-1]
reverse(array, n, size-1);
}
// reverse elements in the array[pos_from ... pos_to]
void reverse(int array[], int pos_from, int pos_to)
{
...
}
Реализация reverse(int array[], int pos_from, int pos_to) с использованием свопов остается в качестве упражнения для читателя. Подсказка: это можно сделать в линейном времени.
Ответ 2
Скажем, у нас есть функция, называемая arr_reverse(arr,i,j), которая меняет элементы массива arr между индексами i и j с помощью функции swap.
Пример:
arr = {1,2,3,4,5}
i = 0
j = 2
то функция вернется:
{3,2,1,4,5}
^^^^^
Реализация этой функции выполняется прямо и O(N).
Теперь можно использовать эту функцию при вращении массива.
arr = {1,2,3,4,5} // input array
k = 2 // amount of right rotation
result = {4,5,1,2,3} // expected result
l = 5 // length of array.
Step 1: Call arr_reverse(arr,l-k,l-1) which is arr_reverse(arr,3,4)
we get {1,2,3,5,4}
^^^
Step 2: Call arr_reverse(arr,0,l-k-1) which is arr_reverse(arr,0,2)
we get {3,2,1,5,4}
^^^^^
Step 3: Call arr_reverse(arr,0,l-1) which is arr_reverse(arr,0,4)
we get {4,5,1,2,3}
^^^^^^^^^
Весь процесс использует arr_reverse 3 раза, делая его O(N)
Ответ 3
Здесь лучшее решение, другого характера, чем другие. Он включает в себя меньшее количество свопов, чем другие. Python:
import fractions
# rotates an array in-place i positions to the left, in linear time
def rotate(arr,i):
n = len(arr)
reps = fractions.gcd(n,i)
swaps = n / reps
for start in xrange(reps):
ix = start
tmp = arr[ix]
for s in xrange(swaps-1):
previx = ix
ix = (ix + i) % n
arr[previx] = arr[ix]
arr[ix] = tmp
return arr
Ответ 4
Используя линейное время O (2N + m) и постоянное пространство O (4). m = GCD (n, p)
Это на 50% быстрее, чем подкачка, потому что для замены требуется запись O (N) раз в временный.
http://www.eis.mdx.ac.uk/staffpages/r_bornat/oldteaching/I2A/slides%209%20circshift.pdf
for (m=0, count=0; count!=n; m++) {
type t=A[m];
for (i=m, j=m+p; j!=m; i=j, j = j+p<n ? j+p : j+p-n, count++)
A[i]=A[j];
A[i]=t; count++;
}
Ответ 5
наивная реализация псевдокода:
for (n = 0; n < i; n++) {
for (j = array.length-1; j > n; j--)
swap(j, j-1)
}
Повторно перемещает последний элемент вперед, останавливаясь перед тем, как он перемещает все ранее перемещенные на передний план
Ответ 6
Лучше использовать прямую и простую функцию, сложность N:
int rotate(int* a,int DIM,int rn,int* b) {
int i; //counter
for(i=0;i<DIM;i++){ // looping through the array
b[(i+rn)%len]=a[i]; // copying the values in the b array=a shifted with rn(+ for right or - for left shifting
}
Ответ 7
public int[] shift(int[] A, int K) {
int N = A.length;
if (N == 0)
return A;
int mid = -K % N;
if (mid < 0)
mid += N;
if (mid == 0)
return A;
reverseSubArray(A, 0 , mid - 1);
reverseSubArray(A, mid , N - 1);
reverseSubArray(A, 0 , N - 1);
return A;
}
private void reverseSubArray(int[] A, int start , int end){
int i = 0;
int tmp;
while (i < (end - start + 1) / 2) {
tmp = A[i + start];
A[i + start] = A[end - i];
A[end - i] = tmp;
i++;
}
}
Ответ 8
Этот алгоритм (не более) len(array)-1 меняет местами и работает как с положительными (справа), так и с отрицательными (слева) значениями поворота. Массив изменен на месте.
Он не требует вычисления GCD, в отличие от других подобных методов.
(Python 3)
def rotate(array,amount):
if amount<0:
amount+=len(array)
a=0
b=0
for _ in range(len(array)-1):
b=(b+amount) % len(array)
if b==a:
a+=1
b=a
if b!=a:
array[a],array[b] = array[b],array[a] #swap array[a],array[b]
return array
Если одного цикла недостаточно (если он возвращается к началу до достижения каждого индекса), начните новый цикл со следующего индекса.
Примечание: вращать элементы a, b, c, d,... можно с помощью
swap a,b swap a,c swap a,d...
Ответ 9
Короткий ответ (код Python)
def reverse(arr, i, j):
for idx in xrange((j - i + 1) / 2):
arr[i+idx], arr[j-idx] = arr[j-idx], arr[i+idx]
def solution(A, K):
l = len(A)
if l == 0:
return []
K = K%l
reverse(A, l - K, l -1)
reverse(A, 0, l - K -1)
reverse(A, 0, l - 1)
return A
Длинный ответ (объяснение кода)
Позвольте мне сначала поговорить о базовом случае с K < N, идея в этом случае состоит в том, чтобы разбить массив на две части A и B, A - это первый массив элементов N-K, а B - последний K элементы. алгоритм переворачивает A и B по отдельности и, наконец, полностью переворачивает массив (две части обращаются по отдельности). Чтобы справиться с делом с помощью K > N, подумайте, что каждый раз, когда вы обращаетесь к массиву N раз, вы снова получаете исходный массив, поэтому мы можем просто использовать оператор модуля, чтобы найти, где разбить массив (обращая вспять только действительно полезные времена, избегая бесполезное переключение).
Графический пошаговый пример может помочь лучше понять концепцию. Обратите внимание, что
- Жирная линия указывает точку разделения массива (в данном примере K = 3);
- Два красных массива указывают соответственно ввод и ожидаемый вывод.
Начиная с:
посмотрите, что перед конечным выводом мы хотим, чтобы последние 3 буквы были перевернутыми, а пока давайте поменяем их на месте (первая обратная сторона алгоритма):
Теперь поменяйте местами первые N-K элементов (второй обратный алгоритм):
у нас уже есть решение, но в обратном направлении мы можем решить его, обращая весь массив (третий и последний обратный алгоритм):
Здесь окончательный вывод, исходный массив циклически вращается с помощью K = 3.
Давайте приведем еще один пошаговый пример с кодом Python, начиная с:
A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
K = 22
N = len(A)
мы находим индекс расщепления:
K = K%N
#2
поскольку в этом случае первые 20 смен будут бесполезными, теперь мы обратим вспять последние K (2) элементы исходного массива:
reverse(A, N-K, N-1)
# [1, 2, 3, 4, 5, 6, 7, 8, 10, 9]
как вы можете видеть, 9 и 10 были сдвинуты, теперь мы возвращаем первые N-K элементы:
reverse(A, 0, N-K-1)
# [8, 7, 6, 5, 4, 3, 2, 1, 10, 9]
И, наконец, мы полностью изменим массив:
reverse(A, 0, N-1)
# [9, 10, 1, 2, 3, 4, 5, 6, 7, 8]
Обратите внимание, что обращение массива имеет временную сложность O (N).
Ответ 10
почему только функция подкачки?
O (n) во времени и пространстве:
var rotateCount = 1;
var arr = new Array(1,2,3,4,5,6,7,8,9,10);
tmp = new Array(arr.length);
for (var i = 0; i<arr.length; i++)
tmp[(i+rotateCount)%arr.length]=arr[i];
arr = tmp;
alert(arr);
Ответ 11
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package rotateinlineartime;
/**
*
* @author Sunshine
*/
public class Rotator {
void reverse(int a[], int n) {
for (int i = 0; i <= n - 1; i++) {
int temp;
temp = a[i];
a[i] = a[n - 1];
a[n - 1] = temp;
n--;
}
printArray(a);
}
void printArray(int a[]) {
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
}
Ответ 12
/* Q: How can we shift/rotate an array in place?
A: "in place" means O(1) space complexity, so we need to do some trick
*/
#include <iostream>
#include <algorithm>
using namespace std;
void ArrayRotate(int a[], int n, int k)
{
if (n < 1 || k % n == 0 ) return;
k %= n;
if (k < 0) k += n;
reverse(a, a+k);
reverse(a+k, a+n);
reverse(a, a+n);
}
void PrintArray(int a[], int n)
{
for ( int i = 0 ; i < n; ++i)
cout << a[i] << " ";
cout << endl;
}
int main()
{
int a[] = { 1, 2 , 3, 4, 5 };
int n = sizeof(a)/sizeof (a[0]);
PrintArray(a, n);
ArrayRotate(a, n, 2);
PrintArray(a, n);
return 0;
}
/* Output:
1 2 3 4 5
3 4 5 1 2
*/
Ответ 13
используя только swap, следующая реализация С++
template<class T>
void rotate_array(std::vector<T> *array, int i) {
int n = array->size();
i = i % n;
int gcd_n_i = gcd(i, n);
for (int j = 0; j < gcd_n_i; j++) {
T first_element = array->at(j);
for (int k = j; (k + i) % n != j; k = (k + i) % n) {
std::swap(array->at(k), array->at((k + i) % n));
}
}
}
Подробнее об этом можно узнать на http://pointer-overloading.blogspot.in/2013/09/algorithms-rotating-one-dimensional.html
Ответ 14
void reverse_array(int a[], int start, int end){
while(start < end){
int temp = a[start];
a[start] = a[end];
a[end] = temp;
start++;
end--;
}
}
void rotate_array(int a[], int pivot, int len){
int i;
/*Reverse the whole array */
reverse_array(a, 0, len);
/* Reverse from 0 to pivot and pivot to end */
reverse_array(a,0, pivot);
reverse_array(a,pivot+1,len);
}
Ответ 15
Здесь небольшой фрагмент, который работает в O (n), написанный на JavaScript. Keyconcept - это то, что вам всегда нужно работать с замененным элементом.
function swap(arr, a, v) {
var old = arr[a];
arr[a] = v;
return old;
}
function rotate(arr, n) {
var length = arr.length;
n = n % length;
if(!n) return arr;
for(var cnt = 0,
index = 0,
value = arr[index],
startIndex = index;
cnt < length;
cnt++) {
// Calc next index
var nextIndex = mapIndex(index, n, length);
// Swap value with next
value = swap(arr, nextIndex, value)
if(nextIndex == startIndex) {
startIndex = index = mapIndex(index, 1, length);
value = arr[index];
} else {
index = nextIndex;
}
}
return arr;
}
function mapIndex(index, n, length) {
return (index - n + length) % length;
}
console.log(rotate([1,2,3,4,5,6,7,8,9], 5))
console.log(rotate([1,2,3,4,5,6], 2))
Ответ 16
Метод O(1) для выполнения этого в python:
class OffsetList(list):
__slots__ = 'offset'
def __init__(self, init=[], offset=-1):
super(OffsetList, self).__init__(init)
self.offset = offset
def __getitem__(self, key):
return super(OffsetList, self).__getitem__(key + self.offset)
def __setitem__(self, key, value):
return super(OffsetList, self).__setitem__(key + self.offset, value)
def __delitem__(self, key):
return super(OffsetList, self).__delitem__(key + self.offset)
def index(self, *args):
return super(OffsetList, self).index(*args) - self.offset
Это основан на этом ответе об использовании 1-основанного списка в python.
У этого есть небольшой сбой, который, если вы попытаетесь индексировать элемент в конце списка, он вернет элементы из (нового) начала, а отрицательные знаки меньше размера минус смещение не будет работать.
Ответ 17
вот мой ответ, используя js hope this help где k - число поворотов, которые вы хотите преформировать
var arrayRoatate=function(array,k){
for(;k>0;k--) {
var nextElementValue=undefined;
for (var i = 0; i < array.length; i=i+2) {
var nextElement = i + 1;
if (nextElement >= array.length)
nextElement = nextElement - array.length;
var tmp=array[i];
if(nextElementValue!==undefined)
array[i]=nextElementValue
nextElementValue=array[nextElement];
array[nextElement]=tmp;
}
}
return array;
Ответ 18
Для кругового вращения справа.
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int k = scan.nextInt() % n;
int q = scan.nextInt();
int arr[] = new int[n];
for (int i = 0; i < n; i++)
{
int a = i + k;
int pos = (a < n) ? a : a - n;
arr[pos] = scan.nextInt();
}
for (int j = 0; j < q; j++)
{
System.out.println(arr[scan.nextInt()]);
}
}
Ответ 19
Мое решение с Java
static int[] rotLeft(int[] a, int d) {
for (int i = 0; i < d; i++) {
oneRotation(a);
}
return a;
}
static void oneRotation(int[] a) {
int firstElement = a[0];
for (int i = 0; i < a.length - 1; i++) {
a[i] = a[i + 1];
}
a[a.length - 1] = firstElement;
}
Ответ 20
public static String rotateKTimes(String str,int k){
int n = str.length();
//java substring has O(n) complexity
return str.substring(n-k) + str.substring(0,n-k);
}
Ответ 21
Simple Solution in O(n) time and using O(1) space:
for e.g 1,2,3,4,5,6,7
rotating 2 times
start with index 2, store a[0] as last
Iteration 1: 1,2,1,4,3,6,5 (1-->3-->5-->7)
Iteration 2: 1,7,1,2,3,4,5 (2-->4-->6)
replace 1 with 6 (last value).
public int[] roatateArray(int[] a,int k)
{
int last = a[0];
int start = k;
for(int j=0;j<k;j++) {
for(int i=start;i<a.length;i+=k)
{
int tmp=a[i];
a[i]=last;
last=tmp;
}
start--;
if (start<=0) break;
}
a[0]=last;
return a;
}