0

面接準備中。object-CIe input =[1,2,2,1,2,3,3,4] output =[1,2,1] を使用して、「配列から連続した重複を排除する最速の方法」という質問の解決策を見つけよう,2,3,4]

  1. 配列内アプローチの場合: 配列内の要素をループします。要素 == 前の要素の場合は、それを削除し、他のすべての要素を再調整してステップを下げます。

  2. 別の配列を使用できるアプローチの場合。要素 == 前の要素の場合、新しい「一意の配列」に追加しないでください。それ以外の場合は、一意の配列に追加します。

より良い解決策はありますか？コードは以下です。可能な最適化はありますか？

別の配列の使用

//Pseudocode for sucessive dup elimination when using another array 
    //
    //duplicateLessArray = empty array
    //previous element = not set
    //
    //for (loop through each element in origArray)
    //  if(previous element == not set or element != previous element)
    //    set previousElement = element 
    //    add element to duplicateLessArray
    //  

    NSMutableArray *duplicateLessArray ;

    duplicateLessArray = [[NSMutableArray alloc] init] ;

    for (NSNumber *nextNumber in origArray)
    {
          if ([nextNumber intValue] != [[duplicateLessArray lastObject] intValue])
          {
            [duplicateLessArray addObject:nextNumber] ;
          }
     }

 NSLog(@"Duplicate less array = %@",duplicateLessArray) ;

同じ配列の使用

    //Pseudocode for in array sucessive dup elimination
    //
    //previous element = not set
    //
    //for (loop through each element in origArray)
    //  if(previous element == not set or element != previous element)
    //    set previousElement = element 
    //  else
    //      delete it from origArray
    //      move back all elements by 1

        NSInteger numElementsInDupLessArray = 0 ;
        NSNumber *prevElement ;
        for (NSNumber *nextNumber in [origArray copy])
        {
          if (numElementsInDupLessArray == 0 || [nextNumber intValue] != [prevElement intValue])
          {
            prevElement=nextNumber ;
            numElementsInDupLessArray++;
          }
          else
          {
            [origArray removeObjectAtIndex:numElementsInDupLessArray] ;
          } 
        }

   NSLog(@"Duplicate less array = %@",origArray) ;
4

1 に答える 1

2

配列内アプローチの最適化があります。

要素を 1 つずつ削除する代わりに (これは O(n^2) の複雑さを引き起こす可能性があります)、単一の要素をシフトするだけです。
擬似コード:

numOfRemoved = 0
GoodValue = A[0]
for i = 1 to arrayEnd //note start from 2nd element
  if A[i] = GoodValue then
    numOfRemoved++
  else
    GoodValue = A[i]
    A[i-numOfRemoved] = A[i]
Resize array once to (Length - numOfRemoved)

例 (' は現在の要素を示し、nr は numOfRemoved です)

[5 5 1 7 7 7 4]   nr = 0  ; 5 stays at index 0
[5 '5 1 7 7 7 4]  nr = 0->1
[5 5 '1 7 7 7 4]  nr = 1 ; 1 goes to index 2-1 = 1
[5 1 1 '7 7 7 4]  nr = 1 ; 7 goes to index 2  
[5 1 7 7 '7 7 4]  nr = 1->2
[5 1 7 7 7 '7 4]  nr = 2->3
[5 1 7 4 7 7 '4]  nr = 3 ; 4 goes to index 6-3 = 3
[5 1 7 4]         resize
于 2016-04-17T03:58:59.193 に答える