算法:从数组中删除重复整数的有效方法

怎么样:

void rmdup(int *array, int length)
{
    int *current , *end = array + length - 1;

    for ( current = array + 1; array < end; array++, current = array + 1 )
    {
        while ( current <= end )
        {
            if ( *current == *array )
            {
                *current = *end--;
            }
            else
            {
                current++;
            }
        }
    }
}

应该是o(n^2)或更小。

我女朋友建议的解决方案是合并类型的变体。唯一的修改是在合并步骤中,忽略重复的值。这个解决方案也是O(n log n)。在这种方法中,将排序/重复删除结合在一起。不过,我不确定这是否有什么区别。

我以前发布过一次,但是我会在这里复制它,因为它很酷。它使用散列,在适当的地方构建类似散列集的东西。它保证在腋窝空间中是O(1)(递归是一个尾部调用),并且通常是O(n)时间复杂性。算法如下:

1. 取数组的第一个元素,这就是哨兵。
2. 尽可能对数组的其余部分重新排序,使每个元素都位于与其哈希相对应的位置。完成此步骤后,将发现重复项。将它们设置为Sentinel。
3. 将索引等于哈希的所有元素移动到数组的开头。
4. 将所有等于sentinel的元素(数组的第一个元素除外)移动到数组的末尾。
5. 在正确散列的元素和重复的元素之间剩下的将是由于冲突而无法放置在与其散列相对应的索引中的元素。重复处理这些元素。

这可以证明是O(N),前提是散列中没有病理场景:即使没有重复,在每次递归中大约会消除2/3的元素。每一级递归都是O(n),其中small n是剩余元素的数量。唯一的问题是,在实践中,它比快速排序慢,当有很少的重复,即大量的碰撞。然而,当有大量的副本时,它的速度是惊人的快。

编辑:在当前的D实现中,哈希T是32位。关于这个算法的所有内容都假定在完整的32位空间中只有很少的哈希冲突(如果有的话)。然而,碰撞可能经常发生在模空间中。然而,对于任何合理大小的数据集,这个假设都很可能是正确的。如果密钥小于或等于32位,它可以是自己的哈希,这意味着在整个32位空间中不可能发生冲突。如果它更大,您就无法将它们中的足够多放入32位内存地址空间中,使其成为一个问题。我假设在D的64位实现中,散列值将增加到64位,数据集可以更大。此外,如果事实证明这是一个问题,那么可以在每个递归级别上更改哈希函数。

下面是D编程语言的一个实现:

void uniqueInPlace(T)(ref T[] dataIn) {
    uniqueInPlaceImpl(dataIn, 0);
}

void uniqueInPlaceImpl(T)(ref T[] dataIn, size_t start) {
    if(dataIn.length - start < 2)
        return;

    invariant T sentinel = dataIn[start];
    T[] data = dataIn[start + 1..$];

    static hash_t getHash(T elem) {
        static if(is(T == uint) || is(T == int)) {
            return cast(hash_t) elem;
        } else static if(__traits(compiles, elem.toHash)) {
            return elem.toHash;
        } else {
            static auto ti = typeid(typeof(elem));
            return ti.getHash(&elem);
        }
    }

    for(size_t index = 0; index < data.length;) {
        if(data[index] == sentinel) {
            index++;
            continue;
        }

        auto hash = getHash(data[index]) % data.length;
        if(index == hash) {
            index++;
            continue;
        }

        if(data[index] == data[hash]) {
            data[index] = sentinel;
            index++;
            continue;
        }

        if(data[hash] == sentinel) {
            swap(data[hash], data[index]);
            index++;
            continue;
        }

        auto hashHash = getHash(data[hash]) % data.length;
        if(hashHash != hash) {
            swap(data[index], data[hash]);
            if(hash < index)
                index++;
        } else {
            index++;
        }
    }


    size_t swapPos = 0;
    foreach(i; 0..data.length) {
        if(data[i] != sentinel && i == getHash(data[i]) % data.length) {
            swap(data[i], data[swapPos++]);
        }
    }

    size_t sentinelPos = data.length;
    for(size_t i = swapPos; i < sentinelPos;) {
        if(data[i] == sentinel) {
            swap(data[i], data[--sentinelPos]);
        } else {
            i++;
        }
    }

    dataIn = dataIn[0..sentinelPos + start + 1];
    uniqueInPlaceImpl(dataIn, start + swapPos + 1);
}

更有效的实施

int i, j;

/* new length of modified array */
int NewLength = 1;

for(i=1; i< Length; i++){

   for(j=0; j< NewLength ; j++)
   {

      if(array[i] == array[j])
      break;
   }

   /* if none of the values in index[0..j] of array is not same as array[i],
      then copy the current value to corresponding new position in array */

  if (j==NewLength )
      array[NewLength++] = array[i];
}

在这个实现中,不需要对数组进行排序。 此外,如果发现重复的元素,则不需要将所有元素在此之后移动一个位置。

此代码的输出是大小为newLength的数组[]

这里我们从数组中的第二个元素开始,并将其与数组中的所有元素进行比较,直到这个数组为止。 我们保存了一个额外的索引变量“newlength”,用于修改输入数组。 newlength variabel初始化为0。

数组[1]中的元素将与数组[0]进行比较。 如果它们不同,则数组[newlength]中的值将使用数组[1]进行修改,并增加newlength。 如果它们相同,则不会修改newLength。

所以如果我们有一个数组[1 2 1 3 1], 然后

在“j”循环的第一个循环中,将数组[1](2)与数组0进行比较,然后将2写入数组[newLength]=数组[1] 所以数组将是[12],因为newLength=2

在“j”循环的第二遍中,数组[2](1)将与数组0和数组1进行比较。这里,因为数组[2](1)和数组0是相同的,所以这里将中断循环。 所以数组将是[12],因为newLength=2

等等。

如果您正在寻找高级的O符号,那么使用O(n log n)排序对数组进行排序,然后执行O(n)遍历可能是最好的路由。如果不进行排序,您将看到O(n^2)。

编辑:如果你只是做整数,那么你也可以做基数排序得到O(N)。

1。使用O(1)额外空间,在O(n log n)时间内

这是可能的,例如:

• 首先进行就地O(N日志N)排序
• 然后遍历该列表一次,将每个实例的第一个实例写回列表的开头

我相信EJEL的合作伙伴是正确的,这样做的最好方法是使用简化的合并步骤进行就地合并排序,这可能是问题的目的,如果您是这样的话,例如编写一个新的库函数来尽可能高效地进行合并,而没有能力改进输入,而且在某些情况下它将是有用的。在没有哈希表的情况下执行此操作,具体取决于输入的种类。但我还没检查过这个。

2。在O(n)时间内使用O(大量)额外空间

• 声明一个大到可以容纳所有整数的零数组
• 穿过阵列一次
• 将每个整数对应的数组元素设置为1。
• 如果已经是1,则跳过该整数。

这仅在以下几个可疑假设成立时有效:

• 可以便宜地将内存归零,或者与整数的数量相比,整数的大小很小。
• 您很高兴向操作系统请求256^sizepof(int)内存
• 如果它是巨大的,它会非常有效地为你缓存它。

这是一个错误的答案,但是如果你有很多输入元素,但是它们都是8位整数(或者甚至可能是16位整数),这可能是最好的方法。

三。O(小)ish额外空间,O(n)ish时间

作为2,但使用哈希表。

4。清晰的道路

如果元素的数目很小,那么如果其他代码写得更快、读得更快,那么编写适当的算法就没有用处。

例如,遍历数组中每个唯一的元素(即第一个元素、第二个元素(第一个元素的副本已删除)等),删除所有相同的元素。o(1)额外空间,o(n^2)时间。

使用能做到这一点的库函数。效率取决于你容易得到的东西。

嗯,它的基本实现非常简单。检查所有元素,检查其余元素是否重复,并将其余元素移到它们上面。

它的效率非常低,您可以使用辅助数组来加速输出或排序/二进制树,但这似乎是不允许的。

如果愿意牺牲内存,可以在一次遍历中完成。您可以简单地计算在哈希/关联数组中是否看到整数。如果您已经看到一个数字,请在移动时将其删除,或者更好地说,将您没有看到的数字移动到新数组中,避免在原始数组中发生任何移动。

在Perl:

foreach $i (@myary) {
    if(!defined $seen{$i}) {
        $seen{$i} = 1;
        push @newary, $i;
    }
}

如果允许使用C++,则调用 std::sort 然后打电话给 std::unique 会给你答案的。排序的时间复杂度为O(n log n),唯一遍历的时间复杂度为O(n)。

如果C++是不存在的,没有任何东西可以阻止这些相同的算法在C中被写入。

函数的返回值应该是唯一元素的数目,它们都存储在数组的前面。如果没有这些额外的信息,您甚至不知道是否有任何重复。

外循环的每个迭代处理数组的一个元素。如果它是唯一的,它将保持在数组的前面;如果它是重复的,它将被数组中最后一个未处理的元素覆盖。此解决方案在O(n^2)时间内运行。

#include <stdio.h>
#include <stdlib.h>

size_t rmdup(int *arr, size_t len)
{
  size_t prev = 0;
  size_t curr = 1;
  size_t last = len - 1;
  while (curr <= last) {
    for (prev = 0; prev < curr && arr[curr] != arr[prev]; ++prev);
    if (prev == curr) {
      ++curr;
    } else {
      arr[curr] = arr[last];
      --last;
    }
  }
  return curr;
}

void print_array(int *arr, size_t len)
{
  printf("{");
  size_t curr = 0;
  for (curr = 0; curr < len; ++curr) {
    if (curr > 0) printf(", ");
    printf("%d", arr[curr]);
  }
  printf("}");
}

int main()
{
  int arr[] = {4, 8, 4, 1, 1, 2, 9};
  printf("Before: ");
  size_t len = sizeof (arr) / sizeof (arr[0]);
  print_array(arr, len);
  len = rmdup(arr, len);
  printf("\nAfter: ");
  print_array(arr, len);
  printf("\n");
  return 0;
}

这里是一个Java版本。

int[] removeDuplicate(int[] input){

        int arrayLen = input.length;
        for(int i=0;i<arrayLen;i++){
            for(int j = i+1; j< arrayLen ; j++){
                if(((input[i]^input[j]) == 0)){
                    input[j] = 0;
                }
                if((input[j]==0) && j<arrayLen-1){
                        input[j] = input[j+1];
                        input[j+1] = 0;
                    }               
            }
        }       
        return input;       
    }

显然,数组应该从右向左“遍历”,以避免来回不必要地复制值。

如果您有无限的内存,您可以为 sizeof(type-of-element-in-array) / 8 每个位的字节表示您是否已经遇到了相应的值。

如果不这样做,我想不出比遍历一个数组并将每个值与后面的值进行比较更好的方法,如果发现重复的值,就完全删除这些值。这是附近的地方 O(n^2) (或) O((n^ 2-n)/ 2) )

IBM有一个 article 有点接近主题。

让我们看看:

• o(n)通过查找最小/最大分配
• 找到的位数组
• o(n)通过将重复数据交换到末尾。

这是我的解决方案。

///// find duplicates in an array and remove them

void unique(int* input, int n)
{
     merge_sort(input, 0, n) ;

     int prev = 0  ;

     for(int i = 1 ; i < n ; i++)
     {
          if(input[i] != input[prev])
               if(prev < i-1)
                   input[prev++] = input[i] ;                         
     }
}

在Java中,我会像这样解决它。不知道怎么用C写这个。

   int length = array.length;
   for (int i = 0; i < length; i++) 
   {
      for (int j = i + 1; j < length; j++) 
      {
         if (array[i] == array[j]) 
         {
            int k, j;
            for (k = j + 1, l = j; k < length; k++, l++) 
            {
               if (array[k] != array[i]) 
               {
                  array[l] = array[k];
               }
               else
               {
                  l--;
               }
            }
            length = l;
         }
      }
   }

这可以用O(n log n)算法一次完成,不需要额外的存储。

从元素开始 a[1] 到 a[N] . 在每个阶段 i ,左边的所有元素 a[i] 包含已排序的元素堆 a[0] 通过 a[j] . 同时,第二个指数 j 最初为0,跟踪堆的大小。

检查 A[一] 并将其插入堆中,该堆现在占用元素 A〔0〕 到 a[j+1] . 当插入元素时,如果元素重复 a[k] 遇到具有相同值的,不要插入 [我] 放入堆中(即丢弃它);否则将其插入堆中,堆现在由一个元素增长,现在由 A〔0〕 到 a [ j+1 ] 和增量 J .

以这种方式继续,递增 我 直到所有的数组元素都被检查并插入到堆中,最终占据 A〔0〕 到 [j] . J 是堆的最后一个元素的索引,堆只包含唯一的元素值。

int algorithm(int[] a, int n)
{
    int   i, j;  

    for (j = 0, i = 1;  i < n;  i++)
    {
        // Insert a[i] into the heap a[0...j]
        if (heapInsert(a, j, a[i]))
            j++;
    }
    return j;
}  

bool heapInsert(a[], int n, int val)
{
    // Insert val into heap a[0...n]
    ...code omitted for brevity...
    if (duplicate element a[k] == val)
        return false;
    a[k] = val;
    return true;
}

看这个例子,这不是所要求的,因为结果数组保留了原始元素顺序。但是如果这一要求得到放宽,上面的算法就应该做到这一点。

下面怎么样?

int* temp = malloc(sizeof(int)*len);
int count = 0;
int x =0;
int y =0;
for(x=0;x<len;x++)
{
    for(y=0;y<count;y++)
    {
        if(*(temp+y)==*(array+x))
        {
            break;
        }
    }
    if(y==count)
    {
        *(temp+count) = *(array+x);
        count++;
    }
}
memcpy(array, temp, sizeof(int)*len);

我尝试声明一个临时数组,并将元素放入其中,然后再将所有内容复制回原始数组。

在回顾了这个问题之后,下面是我的Delphi方法,可能会有所帮助

var
A: Array of Integer;
I,J,C,K, P: Integer;
begin
C:=10;
SetLength(A,10);
A[0]:=1; A[1]:=4; A[2]:=2; A[3]:=6; A[4]:=3; A[5]:=4;
A[6]:=3; A[7]:=4; A[8]:=2; A[9]:=5;

for I := 0 to C-1 do
begin
  for J := I+1 to C-1 do
    if A[I]=A[J] then
    begin
      for K := C-1 Downto J do
        if A[J]<>A[k] then
        begin
          P:=A[K];
          A[K]:=0;
          A[J]:=P;
          C:=K;
          break;
        end
        else
        begin
          A[K]:=0;
          C:=K;
        end;
    end;
end;

//tructate array
setlength(A,C);
end;

下面的示例将解决您的问题:

def check_dump(x):
   if not x in t:
      t.append(x)
      return True

t=[]

output = filter(check_dump, input)

print(output)
True

import java.util.ArrayList;


public class C {

    public static void main(String[] args) {

        int arr[] = {2,5,5,5,9,11,11,23,34,34,34,45,45};

        ArrayList<Integer> arr1 = new ArrayList<Integer>();

        for(int i=0;i<arr.length-1;i++){

            if(arr[i] == arr[i+1]){
                arr[i] = 99999;
            }
        }

        for(int i=0;i<arr.length;i++){
            if(arr[i] != 99999){

                arr1.add(arr[i]);
            }
        }

        System.out.println(arr1);
}
    }

这是幼稚的(n*(n-1)/2)解决方案。它使用恒定的额外空间并保持原始顺序。它类似于@byju的解决方案,但不使用 if(){} 阻碍。它还避免将元素复制到自身。

#include <stdio.h>
#include <stdlib.h>

int numbers[] = {4, 8, 4, 1, 1, 2, 9};
#define COUNT (sizeof numbers / sizeof numbers[0])

size_t undup_it(int array[], size_t len)
{
size_t src,dst;

  /* an array of size=1 cannot contain duplicate values */
if (len <2) return len; 
  /* an array of size>1 will cannot at least one unique value */
for (src=dst=1; src < len; src++) {
        size_t cur;
        for (cur=0; cur < dst; cur++ ) {
                if (array[cur] == array[src]) break;
                }
        if (cur != dst) continue; /* found a duplicate */

                /* array[src] must be new: add it to the list of non-duplicates */
        if (dst < src) array[dst] = array[src]; /* avoid copy-to-self */
        dst++;
        }
return dst; /* number of valid alements in new array */
}

void print_it(int array[], size_t len)
{
size_t idx;

for (idx=0; idx < len; idx++)  {
        printf("%c %d", (idx) ? ',' :'{' , array[idx] );
        }
printf("}\n" );
}

int main(void) {    
    size_t cnt = COUNT;

    printf("Before undup:" );    
    print_it(numbers, cnt);    

    cnt = undup_it(numbers,cnt);

    printf("After undup:" );    
    print_it(numbers, cnt);

    return 0;
}

这可以在一次传递中完成,在O(n)时间内以输入中整数的数目完成。 以唯一整数的数目列出和o(n)存储。

从前到后浏览列表,用两个指针“dst”和 “src”初始化为第一个项。从空哈希表开始 “看到的整数”。如果src处的整数不在哈希中, 将其写入DST的插槽,并递增DST。在SRC处添加整数 到散列,然后递增src。重复,直到SRC通过 输入列表。

将所有元素插入 binary tree the disregards duplicates - O(nlog(n)) . 然后通过遍历将它们全部提取回数组中- O(n) . 我假设你不需要保存订单。

使用Bloom过滤器进行哈希运算。这将大大减少内存开销。

在Java中,

    Integer[] arrayInteger = {1,2,3,4,3,2,4,6,7,8,9,9,10};

    String value ="";

    for(Integer i:arrayInteger)
    {
        if(!value.contains(Integer.toString(i))){
            value +=Integer.toString(i)+",";
        }

    }

    String[] arraySplitToString = value.split(",");
    Integer[] arrayIntResult = new Integer[arraySplitToString.length];
    for(int i = 0 ; i < arraySplitToString.length ; i++){
        arrayIntResult[i] = Integer.parseInt(arraySplitToString[i]);
    }

输出: 1、2、3、4、6、7、8、9、10_

希望这会有帮助

创建一个 BinarySearchTree 它有O(N)复杂性。

首先,您应该创建一个数组 check[n] 其中n是要释放重复的数组元素数,并将每个元素(检查数组的)的值设置为1。使用for循环遍历具有重复项的数组,例如其名称为 arr ,并在for循环中编写:

{
    if (check[arr[i]] != 1) {
        arr[i] = 0;
    }
    else {
        check[arr[i]] = 0;
    }
}

这样,就可以将每个副本设置为零。所以唯一要做的就是穿过 ARR 数组并打印所有不等于零的内容。顺序保持不变,需要线性时间(3*n)。

给定n个元素数组,编写一个算法,在时间o(nlogn)内从数组中删除所有重复项。

Algorithm delete_duplicates (a[1....n])
//Remove duplicates from the given array 
//input parameters :a[1:n], an array of n elements.

{

temp[1:n]; //an array of n elements. 

temp[i]=a[i];for i=1 to n

 temp[i].value=a[i]

temp[i].key=i

 //based on 'value' sort the array temp.

//based on 'value' delete duplicate elements from temp.

//based on 'key' sort the array temp.//construct an array p using temp.

 p[i]=temp[i]value

  return p.

在其他元素中,使用“key”在输出数组中维护。考虑到键的长度为o(n),对键和值执行排序所用的时间为o(nlogn)。因此,从数组中删除所有重复项所用的时间是o(nlogn)。

这就是我所得到的,尽管它把我们可以按升序或降序排序的顺序放错了位置。

#include <stdio.h>
int main(void){
int x,n,myvar=0;
printf("Enter a number: \t");
scanf("%d",&n);
int arr[n],changedarr[n];

for(x=0;x<n;x++){
    printf("Enter a number for array[%d]: ",x);
    scanf("%d",&arr[x]);
}
printf("\nOriginal Number in an array\n");
for(x=0;x<n;x++){
    printf("%d\t",arr[x]);
}

int i=0,j=0;
// printf("i\tj\tarr\tchanged\n");

for (int i = 0; i < n; i++)
{
    // printf("%d\t%d\t%d\t%d\n",i,j,arr[i],changedarr[i] );
    for (int j = 0; j <n; j++)
    {   
        if (i==j)
        {
            continue;

        }
        else if(arr[i]==arr[j]){
            changedarr[j]=0;

        }
        else{
            changedarr[i]=arr[i];

        }
    // printf("%d\t%d\t%d\t%d\n",i,j,arr[i],changedarr[i] );
    }
    myvar+=1;
}
// printf("\n\nmyvar=%d\n",myvar);
int count=0;
printf("\nThe unique items:\n");
for (int i = 0; i < myvar; i++)
{
        if(changedarr[i]!=0){
            count+=1;
            printf("%d\t",changedarr[i]);   
        }
}
    printf("\n");
}

如果你有一个好的数据结构,可以快速判断它是否包含一个整数,那就太酷了。也许是某种树。

DataStructure elementsSeen = new DataStructure();
int elementsRemoved = 0;
for(int i=0;i<array.Length;i++){
  if(elementsSeen.Contains(array[i])
    elementsRemoved++;
  else
    array[i-elementsRemoved] = array[i];
}
array.Length = array.Length - elementsRemoved;