在複雜度爲O（n）和時間O（1）的陣列中旋轉左元素

我想解決向左旋轉數組內部元素的問題。示例：array = [1,2,3,4,5,6,7]如果我調用函數rotateToLeft(array[],int numberElements,int count)其中：array是要旋轉的數組，numberElements是要向左旋轉的元素數量，count是數組大小。我正在尋找O（n）複雜度和O（1）耗時的算法。我的第一個解決方案是使用雙向鏈表，但我想知道是否有更好的解決方案。在複雜度爲O（n）和時間O（1）的陣列中旋轉左元素

LinkedList的的等級節點

@interface Node : NSObject 

    @property (nonatomic,assign) int element; 
    @property (nonatomic,strong) Node* next; 
    @property (nonatomic,strong) Node* previous; 

    @end

類來管理鏈表

@interface LinkedList : NSObject 
    @property (nonatomic,strong) Node* tail; 
    @property (nonatomic,strong) Node* root; 

    -(void)addNode:(int)value; 
    -(void)printList; 
    -(void)rotateLeftElementsOnList:(LinkedList*)list elements:(int)numElement; 

    @end 

    @implementation LinkedList 

    -(instancetype)init{ 
     self = [super init]; 
     if (self) { 
      self.tail = nil; 
     } 
     return self; 

    } 

    -(void)addNode:(int)value{ 
     Node* newNode = [[Node alloc] init]; 
     newNode.element = value; 
     newNode.previous = nil; 
     newNode.next = nil; 
     if (self.tail == nil) { 
      newNode.next = nil; 
      newNode.previous = nil; 
      self.tail = newNode; 
      self.root = newNode; 
      return; 

     } 
     self.tail.previous = newNode; 
     newNode.next = self.tail; 
     self.tail = newNode; 
    } 

    -(void)printList{ 
     Node* header = self.root; 
     while(header.previous != nil){ 
      NSLog(@"%d",header.element); 
      header = header.previous; 

     } 
     NSLog(@"%d",header.element); 
    }

/////這是我的職責旋轉元素的它的工作原理，但我想知道有人知道更好的解決辦法，

-(void)rotateLeftElementsOnList:(LinkedList*)list elements:(int)numElement{ 
     Node* header = self.root; 
     int index = 0; 
     while(index < numElement){ 
     header = header.previous; 
     index++; 

    } 
     header.next.previous = nil; 
     header.next = nil; 
     self.root.next = self.tail; 
     self.tail.previous = self.root; 
     self.root = header; 

    }

來源

2017-05-27 ElMA

你可能是指O（n）**時間**和O（1）**空間**。在O（1）時間移動正常數組中的所有元素是不可能的，「複雜性」可以指時間或空間。 – Dukeling

您是否可以在您的示例中包含函數的示例參數以及相應的輸出？ – Dukeling

我不知道objective-c，所以我不能給你提供一個代碼。但這是一個想法。您可以創建一個類，而不是移動陣列，該類將具有2個屬性：類型爲list/array的a和類型爲int的shift。之後，您將有方法get_element(int i)，它將使用shift值得到i-th元素。一個僞代碼看起來像這樣：

class ShiftedArray: 
    int[] a 
    int shift 

    void shift_array(int positions): 
     shift = positions 

    int get_element(int i): 
     return a[(n + i - shift % n) % n]

來源

2017-05-27 15:27:38 giliev

我不知道Objective-C，所以很遺憾，我不能爲您提供代碼片段;但我會解釋你的邏輯：

反向第一個count元素的數量;
反轉剩餘的元素;
現在反轉整個數組。

實施例：陣列是：[1 2 3 4 5 6 7 8]並且要通過轉移，比如，3個地方：

步驟1：[3 2 1 4 5 6 7 8]
步驟2：[3 2 1 8 7 6 5 4]
步驟3：[4 5 6 7 8 1 2 3]

時間複雜度爲O(n)因爲你只需遍歷一次元素即可將其逆轉，空間複雜度爲O(1)，因爲您沒有使用任何附加的輔助存儲空間。希望這有幫助！

來源

2017-05-27 15:38:15

鏈表是一個數組的O（n）導數。這就是這個想法的底線。如果你可以轉換成列表，轉換成一個環，最後一個節點的下一個指針指向頭部。跟蹤只是一個頭指針。如此一來，只需推進頭部指針即可完成換檔。

來源

2017-05-27 16:05:17 danh

在複雜度爲O（n）和時間O（1）的陣列中旋轉左元素

回答

相關問題