java 从未排序的数组中删除重复项
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/33335218/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Remove duplicates from unsorted array
提问by Sean
My method for quickly returning an array of non-duplicates from a given unsorted array only seems to work some of the time:
我从给定的未排序数组中快速返回非重复数组的方法似乎只在某些时候有效：
public static int[] removeDuplicates(int[] arr) {
if (arr.length <= 1) {
return arr;
}
int lastFound = arr[0];
int currPos = 1;
for (int i = 1; i < arr.length; ++i) {
int num = arr[i];
if (lastFound != num) {
lastFound = num;
arr[currPos++] = num;
}
}
return Arrays.copyOf(arr, currPos);
}
When I input:
当我输入：
int[] arr = {0, 1, 1, 0, 1, 1, 2, 2}
int[] arr2 = removeDuplicates(arr);
it will return:
它会返回：
arr2 = {0, 1, 0, 1, 2}
Where it should return (with no duplicates):
它应该返回的地方（没有重复）：
arr2 = {0, 1, 2}
回答by Andy Turner
In order to determine whether to add a value, you are only looking at the previous element (or, rather, the first element in the previous run of equal values).
为了确定是否添加一个值，您只查看前一个元素（或者，更确切地说，是前一次运行的相等值中的第一个元素）。
This means that it will only work if all elements with a given value are contiguous in the array, which they aren't for your example input.
这意味着它只有在具有给定值的所有元素在数组中都是连续的时才有效，它们不适用于您的示例输入。
e.g. it would work for
例如，它适用于
{0, 0, 1, 1, 2} // Sorted.
or
或者
{2, 0, 0, 1, 1} // Unsorted, but all equal elements are together.
In order to make it work, you need to record allelements that you've seen before, not just the one at the start of the previous run, e.g. by storing the seen elements in a Set. However, given that adding an already-present element to a set doesn't change the set, you may as well just add the whole array to the set:
为了使它工作，您需要记录您之前看到的所有元素，而不仅仅是上一次运行开始时的元素，例如，将看到的元素存储在一个集合中。然而，考虑到将一个已经存在的元素添加到集合中不会改变集合，你也可以将整个数组添加到集合中：
LinkedHashSet<Integer> set = new LinkedHashSet<>(Arrays.asList(arr));
or
或者
set.addAll(Arrays.asList(arr)); // If the set already exists.
If you want to return an int[](as opposed to Integer[], which you could get using set.toArray(new Integer[])) you'd need to copy the elements back into an array:
如果你想返回一个int[]（而不是Integer[]，你可以使用它set.toArray(new Integer[])）你需要将元素复制回一个数组：
int[] result = new int[set.size()];
int idx = 0;
for (int value : set) {
result[idx++] = value;
}
return result;
回答by Jiaying Yang
the way to deal with the problem is record each element which appears in the array when iterating through the array,and delete duplicates of the element. Recording the element is using hashtable.
处理问题的方法是记录遍历数组时出现在数组中的每个元素，并删除该元素的重复项。记录元素是使用哈希表。
public int[] removeDups(int[] data){
Hashtable table = new Hashtable();
ArrayList<int> arrayList= new ArrayList<int>(Arrays.asList(array));
for(int i = 0; i < data.length; i++){
if(table.containsKey(arrayList.get(i)){
arrayList.remove(i);
}else{
table.put(arrayList.get(i),true);
}
}
return arrayList.toArray();
}
This way, removing duplicates is easier.
这样，删除重复项就更容易了。
回答by Alex Rashkov
You can use a set of Integers and that will make sure you have only unique values
您可以使用一组整数，这将确保您只有唯一的值
HashSet<Integer> set = new HashSet<Integer>();
for (int i = 1; i < arr.length; ++i) {
set.add(arr[i]);
}
return set.toArray();
Your approach will work with sorted array so if you use Merge sort to sort the elements in the array which will take O(n log n) worst case you can walk the array and exclude any item that is the same as the previous one in the array thus resulting in an array with only unique numbers.
您的方法将适用于已排序的数组，因此如果您使用合并排序对数组中的元素进行排序，这将采用 O(n log n) 最坏的情况，您可以遍历数组并排除与前一个相同的任何项目数组，从而产生一个只有唯一数字的数组。
public int[] removeDuplicates(int[] data) {
// Make sure you have elemens in the array and it's not empty
Arrays.sort(data);
int number = data[0];
ArrayList<Integer> result = new ArrayList<Integer>;
for (int i = 1; i < data.length; ++i) {
if (data[i] != number) {
number = data[i];
result.add(data[i]);
}
}
result.toArray();
}
