在objective-C中从阵列中消除连续重复项的最快方法

Question

准备面试。试图找出一个解决方案的问题"最快的方法来消除连续重复数组"使用客观C.i. e输入=[1,2,2,1,2,3,3,4]输出=[1,2,1,2,3,4]

>

对于数组内方法：循环数组中的元素，若元素==上一个元素，则移除它并重新调整所有其他元素以向下移动。

对于我们可以使用另一个数组的方法。如果element==上一个元素，不要将其添加到新的“唯一数组”，否则将其添加到唯一数组。

有没有更好的解决办法？代码如下。有可能的优化吗？

使用另一个数组

//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) ;

Answer 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)

“NunR”的当前元素已删除（表示当前元素）

[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