複雑なO（n）と時間O（1）の配列の左要素を回転する

Question

配列内の要素を左に回転させる問題を解決しようとしています。例：array = [1,2,3,4,5,6,7]関数を呼び出す場合rotateToLeft(array[],int numberElements,int count)ここで、arrayは回転する配列、numberElementsは左に回転する要素の数、countは配列のサイズです。私はO（n）の複雑さとO（1）時間のかかるアルゴリズムを探しています。私の最初の解決策は、二重にリンクされたリストを使用することですが、よりよい解決策があるかどうかを知りたいと思います。 LinkedListのの

クラスノード

@interface Node : NSObject 

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

    @end 

クラスは、LinkedListの

@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); 
    } 

を管理する/////これは、AN、それは動作しますが、私はかどうかを知りたいの要素を回転させることが私の関数であります

-(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; 

    } 

Answer 1

私は客観的なcを知らないので、コードを提供することはできません。しかしここに考えがあります。配列をシフトする代わりに、list/arrayタイプのaとintのshiftという2つのプロパティを持つクラスを作成できます。その後、shiftの値を使用してi-th要素を取得するメソッドget_element(int i)が表示されます。擬似コードは次のようになります。

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] 

Answer 2

私はObjective-Cのを知らないが、とても残念ながら、私はあなたのコードスニペットを提供することはできません。私はあなたにロジックを説明します：

1. 最初のcount要素数を逆にします。
2. 残りの要素を逆にします。
3. 今すぐアレイ全体を逆にします。

例：、たとえば、3ヶ所[1 2 3 4 5 6 7 8]、あなたがすることによってシフトしたい：

1. ステップ1：[3 2 1 4 5 6 7 8]
2. ステップ2：[3 2 1 8 7 6 5 4]
3. ステップ3：[4 5 6 7 8 1 2 3]
配列です

時間の複雑さはO(n)です追加の補助記憶域を使用していないため、要素を一度トラバースして逆にすると、空間の複雑さはO(1)になります。これが参考になることを願っています！

Answer 3

リンクリストは配列のO（n）派生です。それがこのアイデアの底です。あなたがリストに変換することができたら、最後のノードの次のポインタが頭を指しているリングに変換してください。ヘッドポインタだけを追跡します。これにより、ヘッドポインタを前進させるだけでシフトを達成することができる。