在将其标记为重复之前,请先阅读该问题
我编写了以下代码,以在不使用Util类的情况下从数组中删除重复项,但是现在我被卡住了
public class RemoveDups{
public static void main(String[] args) {
int[] a = { 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 3, 1, 4, 52, 1, 45, };
int temp;
for (int i : a) {
for (int j = 0; j < a.length - 1; j++) {
if (a[j] > a[j + 1]) {
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
a = removeDups(a);
for (int i : a) {
System.out.println(i);
}
}
private static int[] removeDups(int[] a) {
int[] result = new int[a.length];
int j = 0;
for (int i : a) {
if (!isExist(result, i)) {
result[j++] = i;
}
}
return result;
}
private static boolean isExist(int[] result, int i) {
for (int j : result) {
if (j == i) {
return true;
}
}
return false;
}
}
现在的输出是
1
2
3
4
5
6
45
52
0
0
0
0
0
0
0
0
0
0
这是我的问题
由于您处理的数字范围很小,因此您可以通过简单的“计数排序”删除重复项:在类似集合的数据结构中标记找到的数字,然后遍历该数据结构。一组boolean
工作很好,可以减少基本的位集或哈希表来减少内存使用量。如果n是数组中元素的数量,并且m是范围的大小,则此算法的复杂度为O(n + m)。
private static int[] removeDups(int[] a, int maxA) {
boolean[] present = new boolean[maxA+1];
int countUnique = 0;
for (int i : a) {
if (!present[i]) {
countUnique++;
present[i] = true;
}
}
int[] result = new int[countUnique];
int j = 0;
for (int i=0; i<present.length; i++) {
if (present[i]) result[j++] = i;
}
return result;
}
我不明白如何对数组进行排序可以减少执行时间
在排序的数组中,您可以在一次扫描中检测重复项,从而花费O(n)的时间。由于排序比检查每个对要快-O(n log n)与O(n²)的时间复杂度-因此对数组进行排序要比使用朴素算法更快。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句