algorithm：从数组中删除重复整数的有效方法
我在接受微软采访时得到了这个问题。
给定一个随机整数数组，在C中编写一个algorithm，删除重复的数字，并返回原始数组中的唯一数字。
例如：input： {4, 8, 4, 1, 1, 2, 9} 4,8,4,1,1,2,9 {4, 8, 4, 1, 1, 2, 9}输出： {4, 8, 1, 2, 9, ?, ?}
一个警告是，预期的algorithm不应该要求首先sorting数组。 当一个元素被删除时，下面的元素也必须向前移动。 无论如何，元素向前移位的数组尾部元素的值是可以忽略的。
更新：结果必须在原始数组中返回，不应使用帮助器数据结构（例如散列表）。 不过，我猜想保存命令是没有必要的。
更新2：对于那些为什么这些不切实际的约束，这是一个面试问题，所有这些约束在思考过程中讨论，看看我能如何提出不同的想法。
怎么样：
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）或更less。
我的女朋友build议的解决scheme是合并sorting的变化。 唯一的修改是在合并步骤中，忽略重复的值。 这个解决scheme也是O（n log n）。 在这种方法中，分类/重复删除被组合在一起。 不过，我不确定这是否有所作为。
我之前已经发布了这个，但是我会在这里重现它，因为它非常酷。 它使用哈希，像哈希集合就位。 在腋窝空间中保证是O（1）（recursion是尾部调用），并且通常是O（N）时间复杂度。 algorithm如下：
- 取数组的第一个元素，这将是哨兵。
- 尽可能地对数组的其余部分进行重新sorting，以使每个元素位于与其哈希对应的位置。 这一步完成后，会发现重复项。 将它们设置为等同于哨兵。
- 将索引等于散列的所有元素移到数组的开头。
- 将除了数组的第一个元素之外的所有等于标记的元素移到数组的末尾。
- 恰当散列的元素和重复元素之间留下的是由于冲突而无法放置在与其散列对应的索引中的元素。 recursion处理这些元素。
这可以表示为O（N）提供散列中没有病态情况：即使没有重复，每个recursion大约2/3的元素将被消除。 recursion的每个级别是O（n），其中小n是剩余元素的数量。 唯一的问题是，在实践中，当重复次数很less，即大量碰撞时，它比快速sorting要慢。 但是，当有大量重复的时候，速度非常快。
编辑：在D的当前实现中，hash_t是32位。 关于这个algorithm的一切都假定在32位的完整空间中将会有非常less的（如果有的话）散列冲突。 然而，碰撞可能在模数空间中经常发生。 但是，对于任何合理大小的数据集，这种假设很可能是正确的。 如果密钥小于或等于32位，则它可以是它自己的散列，这意味着在完整的32位空间中的冲突是不可能的。 如果它更大，你根本无法把它们放到32位的内存地址空间中，这是一个问题。 我假设在D的64位实现中，hash_t会增加到64位，其中数据集可以更大。 而且，如果这确实certificate是一个问题，那么可以在recursion的每个级别改变散列函数。
这是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); }
如果您正在寻找优越的O-notation，那么使用O（n log n）sorting来sorting数组，然后执行O（n）遍历可能是最好的路线。 没有sorting，你正在看O（n ^ 2）。
编辑：如果你只是做整数，那么你也可以做基数sorting得到O（n）。
一个更有效的实现
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]; }
在这个实现中，不需要对数组进行sorting。 此外，如果find重复的元素，则不需要将此后的所有元素移动一个位置。
这个代码的输出是大小为NewLength的array []
这里我们从数组中的第二个elemt开始，并将它与数组中的所有元素进行比较，直到这个数组。 我们持有一个额外的索引variables“NewLength”来修改input数组。 NewLength variabel被初始化为0。
数组[1]中的元素将与数组[0]进行比较。 如果它们不同，则数组[NewLength]中的值将使用数组[1]进行修改并增加NewLength。 如果相同，NewLength将不会被修改。
所以如果我们有一个数组[1 2 1 3 1]，那么
在'j'循环的第一遍中，将array [1]（2）与array0进行比较，然后将2写入数组[NewLength] = array [1]，因此NewLength = 2之后数组将为[1 2]
在第二遍“j”循环中，array [2]（1）将与array0和array1进行比较。 这里由于数组[2]（1）和array0是相同的循环将在这里打破。 所以从NewLength = 2开始数组将会是[1 2]
等等
1.在O（n log n）时间内使用O（1）额外的空间
这是可能的，例如：
- 首先进行O（n log n）sorting
- 然后遍历列表一次，将每个后面的第一个实例写入列表的开头
我相信ejel的合作伙伴是正确的，最好的方法是通过简化的合并步骤进行就地合并，如果您是例如，那么这可能是问题的意图。 编写一个新的库函数来尽可能有效地完成这些工作，而不能改进input，而且根据input的种类，在没有散列表的情况下这样做会是有用的。 但是我实际上没有检查过这个。
2.在O（n）时间内使用O（大量）额外空间
- 声明一个足够大的零数组来保存所有的整数
- 一次穿过arrays
- 为每个整数设置相应的数组元素为1。
- 如果它已经是1，则跳过该整数。
这只适用于几个可疑的假设：
- 可以便宜地将内存归零，或者整数的大小与它们的数目相比是小的
- 你很高兴向你的操作系统请求256 ^ sizepof（int）内存
- 它会caching它真的非常有效，如果它是巨大的
这是一个不好的答案，但如果你有很多的input元素，但它们都是8位整数（或者甚至16位整数），这可能是最好的方法。
O（小） – 额外的空间，O（N） – 时间
至于＃2，但使用一个哈希表。
4.清晰的方式
如果元素的数量很less，如果其他代码的写入速度更快，读取速度更快，那么编写适当的algorithm就没有用处。
例如。 通过数组遍历每个唯一元素（即第一个元素，第二个元素（第一个元素的副本已被删除）等），删除所有相同的元素。 O（1）额外的空间，O（n ^ 2）时间。
例如。 使用库函数来做到这一点。 效率取决于你可以轻松获得的。
那么，它的基本实现是相当简单的。 仔细检查所有元素，检查其余元素是否有重复，并将剩余的重复。
这是非常糟糕的效率低下，你可以通过输出或sorting/二叉树的辅助数组加速它，但这似乎不被允许。
如果你愿意牺牲记忆，你可以在一次遍历中做到这一点。 你可以简单地理解你是否看到一个整数或不在散列/关联数组中。 如果您已经看到了一个数字，请随时移除它，或者更好地将未看到的数字移动到新数组中，以避免在原始数组中出现任何移位。
在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 ++离开了表，那么就没有任何东西能够保持这些相同的algorithm不被C写入
函数的返回值应该是唯一元素的数量，它们都存储在数组的前面。 没有这些额外的信息，你甚至不知道是否有任何重复。
外循环的每次迭代处理数组的一个元素。 如果它是唯一的，它将停留在数组的前面，如果它是重复的，它会被数组中最后一个未处理的元素覆盖。 这个解决scheme运行在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; }
一个数组显然应该从右到左“遍历”，以避免不必要的值来回复制。
如果你有无限的内存，你可以分配一个sizeof(type-of-element-in-array) / 8数组sizeof(type-of-element-in-array) / 8个字节的位数组来表示每个位是否已经遇到相应的值。
如果你不这样做，我想不出比遍历一个数组，并比较每个值和它后面的值，然后如果发现重复，完全删除这些值。 这在O（n ^ 2） （或O（（n ^ 2-n）/ 2） ）附近。
IBM有一篇关于有点紧密的话题。
让我们来看看：
- O（N）通过查找最小/最大分配
- find的位数组
- O（N）交换重复结束。
这是一个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; }
在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）algorithm一次完成，不需要额外的存储。
从元素a[1]继续到a[N] 。 在每一个阶段i ， a[i]左边的所有元素包含一个元素a[0]到a[j]的sorting堆。 同时，第二个索引j （最初为0）跟踪堆的大小。
检查a[i]并将其插入堆中，现在占用元素a[0]到a[j+1] 。 插入元素时，如果遇到具有相同值的重复元素a[k] ，则不要将a[i]插入堆中（即放弃它）。 否则将其插入到堆中，堆现在由一个元素增长，现在包含a[0]到a[j+1] ，并增加j 。
以这种方式继续，直到所有数组元素都被检查并插入到堆中，最后占用a[j] a[0] a[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; }
看看这个例子，这并不是所要求的，因为结果数组保留了原始的元素顺序。 但是，如果这个要求是放松的，上面的algorithm应该做的伎俩。
以下情况如何？
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
这是我的解决scheme。
///// 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] ; } }
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）解决scheme。 它使用不变的额外空间并保持原来的顺序。 它类似于@Byju的解决scheme，但不使用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; }
这可以一次完成，input列表中整数的O（N）时间，以及整数个唯一整数的O（N）存储。
从头到尾浏览列表，用“dst”和“src”两个指针初始化为第一项。 从“看到整数”的空哈希表开始。 如果散列中不存在src中的整数，则将其写入dst中的插槽并增量dst。 将src中的整数添加到散列，然后增加src。 重复，直到src通过input列表的末尾。
插入binary tree the disregards duplicates所有元素binary tree the disregards duplicates – O(nlog(n)) 。 然后通过遍历 – O(n)将它们全部提取回数组中。 我假设你不需要保存订单。
使用bloomfilter进行散列。 这将非常显着地减less内存开销。
在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}
希望这会有所帮助
创build一个复杂度为O（n）的BinarySearchTree 。
首先，你应该创build一个数组check[n] ，其中n是你想做的不重复的数组元素的数量，并且将每个（检查数组的）元素的值设置为1.使用for循环遍历与重复的数组，说它的名字是arr ，并在for循环写这个：
{ if (check[arr[i]] != 1) { arr[i] = 0; } else { check[arr[i]] = 0; } }
用这个，你设置每一个副本等于零。 所以唯一要做的就是遍历arr数组并打印不等于零的所有东西。 订单保持，需要线性时间（3 * n）。
Given an array of n elements, write an algorithm to remove all duplicates from the array in time 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.
In other of elements is maintained in the output array using the 'key'. Consider the key is of length O(n), the time taken for performing sorting on the key and value is O(nlogn). So the time taken to delete all duplicates from the array is O(nlogn).
this is what i've got, though it misplaces the order we can sort in ascending or descending to fix it up.
#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"); }
It'd be cool if you had a good DataStructure that could quickly tell if it contains an integer. Perhaps a tree of some sort.
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;
