我有一个未排序的数组，删除元素（如果存在）的所有重复项的最佳方法是什么？
例如：
a[1,5,2,6,8,9,1,1,10,3,2,4,1,3,11,3]
所以在该操作之后，数组应该看起来像这样
a[1,5,2,6,8,9,10,3,4,11]
最简单的解决方案是对照每个其他元素检查每个元素。这是浪费并且产生 O(n2) 解决方案，即使你只“前进”。
更好的解决方案是对数组进行排序，然后检查每个元素与其旁边的元素以查找重复项。选择一种有效的排序，这是 O(n log n)。
基于排序的解决方案的缺点是无法维持顺序。然而，一个额外的步骤可以解决这个问题。将所有条目（在唯一排序数组中）放入哈希表中，该哈希表的访问时间复杂度为 O(1)。然后迭代原始数组。对于每个元素，检查它是否在哈希表中。如果是，则将其添加到结果中并从哈希表中删除。您最终将得到一个结果数组，该数组具有原始数组的顺序，每个元素与其第一次出现的位置相同。
如果您正在处理某个固定范围的整数，您可以使用基数排序做得更好。例如，如果假设数字都在 0 到 1,000,000 的范围内，则可以分配大约 1,000,001 的位向量。对于原始数组中的每个元素，您可以根据其值设置相应的位（例如，值 13 会导致设置第 14 位）。然后遍历原数组，检查是否在位向量中。如果是，则将其添加到结果数组中并从位向量中清除该位。这是 O(n)，用空间换取时间。
这使我们找到了最好的解决方案：这种排序实际上是一种干扰，尽管很有用。创建具有 O(1) 访问权限的哈希表。遍历原始链表。如果哈希表中尚不存在，则将其添加到结果数组中，然后将其添加到哈希表中。如果它在哈希表中，则忽略它。
这是迄今为止最好的解决方案。那么为什么剩下的呢？因为像这样的问题是关于将您拥有（或应该拥有）的知识应用于问题，并根据您做出的假设将其改进为解决方案。改进解决方案并理解其背后的想法比反省解决方案有用得多。
此外，哈希表并不总是可用。以嵌入式系统或空间非常有限的系统为例。您可以用少量操作码实现快速排序，这比任何哈希表都少得多。
这可以使用基于哈希表的集合在摊销 O(n) 中完成。
伪代码：
s := new HashSet
c := 0
for each el in a
Add el to s.
If el was not already in s, move (copy) el c positions left.
If it was in s, increment c.
如果您不需要保留原始对象，您可以循环它并创建一个新的唯一值数组。在 C# 中，使用列表来访问所需的功能。这不是最有吸引力或最智能的解决方案，但它确实有效。
int[] numbers = new int[] {1,2,3,4,5,1,2,2,2,3,4,5,5,5,5,4,3,2,3,4,5};
List<int> unique = new List<int>();
foreach (int i in numbers)
if (!unique.Contains(i))
unique.Add(i);
unique.Sort();
numbers = unique.ToArray();
将数字视为键。
for each elem in array:
if hash(elem) == 1 //duplicate
ignore it
next
else
hash(elem) = 1
add this to resulting array
end
array flag[N] //N is the max number in the array
for each elem in input array:
if flag[elem - 1] == 0
flag[elem - 1] = 1
add it to resulatant array
else
discard it //duplicate
end
indexOutput = 1;
outputArray[0] = arrayInt[0];
int j;
for (int i = 1; i < arrayInt.length; i++) {
j = 0;
while ((outputArray[j] != arrayInt[i]) && j < indexOutput) {
j++;
}
if(j == indexOutput){
outputArray[indexOutput] = arrayInt[i];
indexOutput++;
}
}
使用 Set 实现。
HashSet、TreeSet 或 LinkedHashSet（如果是 Java）。
这是我用C++创建的代码段，试试吧
#include <iostream>
using namespace std;
int main()
{
cout << " Delete the duplicate" << endl;
int numberOfLoop = 10;
int loopCount =0;
int indexOfLargeNumber = 0;
int largeValue = 0;
int indexOutput = 1;
//Array to hold the numbers
int arrayInt[10] = {};
int outputArray [10] = {};
// Loop for reading the numbers from the user input
while(loopCount < numberOfLoop){
cout << "Please enter one Integer number" << endl;
cin >> arrayInt[loopCount];
loopCount = loopCount + 1;
}
outputArray[0] = arrayInt[0];
int j;
for (int i = 1; i < numberOfLoop; i++) {
j = 0;
while ((outputArray[j] != arrayInt[i]) && j < indexOutput) {
j++;
}
if(j == indexOutput){
outputArray[indexOutput] = arrayInt[i];
indexOutput++;
}
}
cout << "Printing the Non duplicate array"<< endl;
//Reset the loop count
loopCount =0;
while(loopCount < numberOfLoop){
if(outputArray[loopCount] != 0){
cout << outputArray[loopCount] << endl;
}
loopCount = loopCount + 1;
}
return 0;
}
我的解决方案（
O(N) public class MyArray
{
//data arr
private int[] _arr;
//field length of my arr
private int _leght;
//counter of duplicate
private int countOfDup = 0;
//property length of my arr
public int Length
{
get
{
return _leght;
}
}
//constructor
public MyArray(int n)
{
_arr = new int[n];
_leght = 0;
}
// put element into array
public void Insert(int value)
{
_arr[_leght] = value;
_leght++;
}
//Display array
public void Display()
{
for (int i = 0; i < _leght; i++) Console.Out.Write(_arr[i] + " ");
}
//Insertion sort for sorting array
public void InsertSort()
{
int t, j;
for (int i = 1; i < _leght; i++)
{
t = _arr[i];
for (j = i; j > 0; )
{
if (_arr[j - 1] >= t)
{
_arr[j] = _arr[j - 1];
j--;
}
else break;
}
_arr[j] = t;
}
}
private void _markDuplicate()
{
//mark duplicate Int32.MinValue
for (int i = 0; i < _leght - 1; i++)
{
if (_arr[i] == _arr[i + 1])
{
countOfDup++;
_arr[i] = Int32.MinValue;
}
}
}
//remove duplicates O(N) ~ O(2N) ~ O(N + N)
public void RemoveDups()
{
_markDuplicate();
if (countOfDup == 0) return; //no duplicate
int temp = 0;
for (int i = 0; i < _leght; i++)
{
// if duplicate remember and continue
if (_arr[i] == Int32.MinValue) continue;
else //else need move
{
if (temp != i) _arr[temp] = _arr[i];
temp++;
}
}
_leght -= countOfDup;
}
}
还有主要
static void Main(string[] args)
{
Random r = new Random(DateTime.Now.Millisecond);
int i = 11;
MyArray a = new MyArray(i);
for (int j = 0; j < i; j++)
{
a.Insert(r.Next(i - 1));
}
a.Display();
Console.Out.WriteLine();
a.InsertSort();
a.Display();
Console.Out.WriteLine();
a.RemoveDups();
a.Display();
Console.ReadKey();
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class testing {
public static void main(String[] args) {
EligibleOffer efg = new EligibleOffer();
efg.setCode("1234");
efg.setName("hey");
EligibleOffer efg1 = new EligibleOffer();
efg1.setCode("1234");
efg1.setName("hey1");
EligibleOffer efg2 = new EligibleOffer();
efg2.setCode("1235");
efg2.setName("hey");
EligibleOffer efg3 = new EligibleOffer();
efg3.setCode("1235");
efg3.setName("hey");
EligibleOffer[] eligibleOffer = { efg, efg1,efg2 ,efg3};
removeDupliacte(eligibleOffer);
}
public static EligibleOffer[] removeDupliacte(EligibleOffer[] array) {
List list = Arrays.asList(array);
List list1 = new ArrayList();
int len = list.size();
for (int i = 0; i <= len-1; i++) {
boolean isDupliacte = false;
EligibleOffer eOfr = (EligibleOffer) list.get(i);
String value = eOfr.getCode().concat(eOfr.getName());
if (list1.isEmpty()) {
list1.add(list.get(i));
continue;
}
int len1 = list1.size();
for (int j = 0; j <= len1-1; j++) {
EligibleOffer eOfr1 = (EligibleOffer) list1.get(j);
String value1 = eOfr1.getCode().concat(eOfr1.getName());
if (value.equals(value1)) {
isDupliacte = true;
break;
}
System.out.println(value+"\t"+value1);
}
if (!isDupliacte) {
list1.add(eOfr);
}
}
System.out.println(list1);
EligibleOffer[] eligibleOffer = new EligibleOffer[list1.size()];
list1.toArray(eligibleOffer);
return eligibleOffer;
}
}
Time O(n) space O(n)
#include <iostream>
#include<limits.h>
using namespace std;
void fun(int arr[],int size){
int count=0;
int has[100]={0};
for(int i=0;i<size;i++){
if(!has[arr[i]]){
arr[count++]=arr[i];
has[arr[i]]=1;
}
}
for(int i=0;i<count;i++)
cout<<arr[i]<<" ";
}
int main()
{
//cout << "Hello World!" << endl;
int arr[]={4, 8, 4, 1, 1, 2, 9};
int size=sizeof(arr)/sizeof(arr[0]);
fun(arr,size);
return 0;
}
public class RemoveDuplicateArray {
public static void main(String[] args) {
int arr[] = new int[] { 1, 2, 3, 4, 5, 6, 7, 2, 3, 4, 9 };
int size = arr.length;
for (int i = 0; i < size; i++) {
for (int j = i+1; j < size; j++) {
if (arr[i] == arr[j]) {
while (j < (size) - 1) {
arr[j] = arr[j + 1];
j++;
}
size--;
}
}
}
for (int i = 0; i < size; i++) {
System.out.print(arr[i] + " ");
}
}
}
输出 - 1 2 3 4 5 6 7 9
您可以在 python 中使用“in”和“not in”语法，这使得它非常简单。
复杂度高于散列方法，因为“不在”相当于线性遍历以找出该条目是否存在。
li = map(int, raw_input().split(","))
a = []
for i in li:
if i not in a:
a.append(i)
print a
我是用Python做的。
array1 = [1,2,2,3,3,3,4,5,6,4,4,5,5,5,5,10,10,8,7,7,9,10]
array1.sort() # sorting is must
print(array1)
current = NONE
count = 0
# overwriting the numbers at the frontal part of the array
for item in array1:
if item != current:
array1[count] = item
count +=1
current=item
print(array1)#[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 5, 5, 5, 5, 6, 7, 7, 8, 9, 10, 10, 10]
print(array1[:count])#[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
最有效的方法是：
array1 = [1,2,2,3,3,3,4,5,6,4,4,5,5,5,5,10,10,8,7,7,9,10]
array1.sort()
print(array1)
print([*dict.fromkeys(array1)])#[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
#OR#
aa = list(dict.fromkeys(array1))
print( aa)#[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
使用字典数组并将每个项目添加为键 如果一个项目重复，字典避免添加它！ 这是最好的解决方案
int[] numbers = new int[] {1,2,3,4,5,1,2,2,2,3,4,5,5,5,5,4,3,2,3,4,5};
IDictionary<int, string> newArray = new Dictionary<int, string>();
for (int i = 0; i < numbers.count() ; i++)
{
newArray .Add(numbers[i] , "");
}
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int n=nums.size();
int index=1;
for(int i=1; i<n; i++){
if(nums[i] == nums[i-1]) continue;
nums[index] = nums[i];
index++;
}
return index;
}
};