如何在不使用任何库或集合的情况下从数组中删除所有重复元素

Question

正如标题所说。我想在不使用任何库或集合的情况下从数组中删除所有重复的元素。我通常使用Set或HashMap，但在这种情况下已经不可能了。我还考虑过像一样对数组进行排序和从头到尾的检查

If(arr[i]==a[i+1])
delete arr[i]; i--;

或者用2表示循环。但它们的效率还不够。有没有其他更有效的方法来删除重复项？非常感谢。

Answer 1

如果我们对数组进行排序，则值之间的任何重复都将彼此接近。这样我们就可以去除

int a[] = { 1,9,55,1,8,9,77,2,5,54,7,10,11 };
Arrays.sort(a);
int j = 0;
for (int i = 0; i < a.length - 1; i++) {
if (a[i] != a[i + 1]) {
a[j] = a[i];
j++;
}
}
a[j] = a[a.length - 1];
return a;

Answer 2

如果你可以使用Streams(它们不是集合，从Java 8开始就可以使用(，你可以做这样的事情：

int[] result = Arrays.stream(a).distinct().toArray();

Answer 3

这是另一种可能性。成本是O(n+m(，其中m是输入数组的最大值。

public static void main(String[] args) {
int arr[] = {23, 56, 78, 92, 44, 3, 3, 3, 23, 11, 10, 10, 10, 10};
// Find the size for the new array to allocate.
int max = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
// Mark the values stored in the array (hit or miss array)
int[] presence = new int[max + 1];
for (int i = 0; i < arr.length; i++) {
presence[arr[i]] = 1;
}
// Find the size for the new array to allocate
int count = 0;
for (int i = 0; i < presence.length; i++) {
if (presence[i] != 0) {
count++;
}
}
// Store the element in the new array when hit
int[] res = new int[count];
int index = 0;
for (int i = 0; i < presence.length; i++) {
if (presence[i] != 0) {
res[index] = i;
index++;
}
}
for (int i = 0; i < res.length; i++) {
System.out.print(res[i] + ", ");
}
}

我确信这可以显著改善，但你可以把它作为一个起点。

Answer 4

我们可以使用下面的代码从数组中删除重复项，而不使用任何集合或流。在String类的帮助下完成了。订单也将保留

// Input Array
int a[] = {1, 9, 55, 1, 8, 9, 77, 2, 5, 54, 7, 10, 11};
String s = "";
for (int i = 0; i < a.length; i++) {
String s1 = String.valueOf(a[i]);
if (!s.startsWith(s1 + " ") && !s.contains(" " + s1 + " ")) {
s = s.concat(s1 + " ");
}
}
System.out.println(s);
// output: 1 9 55 8 77 2 5 54 7 10 11