算法 - 圓形陣列旋轉

Question

圓形陣列旋轉的線性複雜性實現是否正確？

N =元素數目 K =轉

int write_to  = 0; 
    int copy_current = 0; 
    int copy_final = a[0]; 
    int rotation  = k; 
    int position  = 0; 

    for (int i = 0; i < n; i++) { 
     write_to  = (position + rotation) % n; 
     copy_current = a[write_to]; 
     a[write_to] = copy_final; 
     position  = write_to; 
     copy_final = copy_current; 
    } 

Answer 1

號

考慮這個例子的數目。

#include <iostream> 

int main(void) { 
    int n = 6; 
    int k = 2; 
    int a[] = {1, 2, 3, 4, 5, 6}; 

    int write_to  = 0; 
    int copy_current = 0; 
    int copy_final = a[0]; 
    int rotation  = k; 
    int position  = 0; 

    for (int i = 0; i < n; i++) { 
     write_to  = (position + rotation) % n; 
     copy_current = a[write_to]; 
     a[write_to] = copy_final; 
     position  = write_to; 
     copy_final = copy_current; 
    } 

    for (int i = 0; i < n; i++) { 
     std::cout << a[i] << (i + 1 < n ? ' ' : '\n'); 
    } 
    return 0; 
} 

預期結果：

5 6 1 2 3 4 

實際結果：

3 2 1 4 1 6 

Answer 2

使用STL ::旋轉上的std ::陣列，可以循環左移的話，比如說2，如：

std::array<int, 6> a{1, 2, 3, 4, 5, 6}; 
std::rotate(begin(a), begin(a) + 2, end(a)); // left rotate by 2 

，得到：3 4 5 6 1 2，或右鍵RO tate by，say 2，as：

std::rotate(begin(a), end(a) - 2, end(a)); // right rotate by 2 

產生：5 6 1 2 3 4，具有線性複雜性。

Answer 3

旋轉數組長度爲n爲k次在left或right方向。

該代碼是用Java

我定義了一個方向枚舉：

旋轉與 times和 direction

public enum Direction { 
    L, R 
}; 

：

public static final void rotate(int[] arr, int times, Direction direction) { 
    if (arr == null || times < 0) { 
     throw new IllegalArgumentException("The array must be non-null and the order must be non-negative"); 
    } 
    int offset = arr.length - times % arr.length; 
    if (offset > 0) { 
     int[] copy = arr.clone(); 
     for (int i = 0; i < arr.length; ++i) { 
      int j = (i + offset) % arr.length; 
      if (Direction.R.equals(direction)) { 
       arr[i] = copy[j]; 
      } else { 
       arr[j] = copy[i]; 
      } 
     } 
    } 
} 

複雜度：O（N ）。

實施例： 輸入：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 旋轉3倍left 輸出：[4, 5, 6, 7, 8, 9, 10, 1, 2, 3]

輸入：[4, 5, 6, 7, 8, 9, 10, 1, 2, 3] 旋轉3倍right 輸出：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]