0

Please read the question before marking it as duplicate

I have written following code to remove duplicates from array without using Util classes but now I am stuck

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;
    }

}

and now the output is 

1
2
3
4
5
6
45
52
0
0
0
0
0
0
0
0
0
0

Here my problem is

  1. My code is not working in case of 0s
  2. I am not able to understand how sorting an array can reduce time of execution
  3. Is there any way to remove elements from array without using Util classes I know one way to remove convert array into list and then remove but for that also we need Util classes is there any way to implement by myself.
4

7 回答 7

3

由于您处理的数字被限制在一个很小的范围内，您可以通过简单的“计数排序”删除重复项：标记您在类似集合的数据结构中找到的数字，然后检查数据结构。一组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²) 时间复杂度相比 - 对数组进行排序而不是使用朴素算法会更快。

于 2013-10-04T09:01:14.543 回答
2
  1. 由于您正在制作与数组 a 长度相同的结果数组，因此即使您只在其中放入唯一项，其余的空白项也会在其中包含重复值，对于 int 数组为 0。
  2. 排序对您没有多大帮助，因为您的代码一次又一次地搜索整个数组以查找重复项。你需要改变你的逻辑。
  3. 您可以首先在结果数组中为所有数组项添加一些负值，例如 -1，然后您可以通过从中删除所有负值轻松地创建一个新的结果数组，例如 finalResult 数组，它还可以帮助您删除所有零。
于 2013-10-04T07:05:50.573 回答
2

在 java 中，数组是固定长度的。一旦创建，它们的大小就无法更改。所以你创建了一个 size18 的数组。然后在你应用你的逻辑之后，一些元素被删除了。但数组大小不会改变。因此，即使删除重复后只有 8 个元素，其余 10 个元素也会自动填充 0 以保持大小为 18。

解决方案 ？

  1. 将新列表存储在另一个大小为 8 的数组中（或其他，计算新数组的大小）
  2. 保留一个新变量以指向最后一个有效元素的末尾，在本例中为 52 的索引。请注意，数组仍将具有 0 值，您只是不会使用它们。

I am not able to understand how sorting an array can reduce time of execution 什么 ？如果需要对数组进行排序，则对数组进行排序。没有其他的。某些算法可能需要对数组进行排序，或者如果对数组进行排序，则可能会更好。取决于您使用阵列的位置。在您的情况下，排序将无济于事。

至于您的最后一个问题，您绝对可以通过搜索元素是否存在多次然后删除所有重复项来实现自己的重复删除。

于 2013-10-04T07:02:19.543 回答
1

我的代码在 0 的情况下不起作用

您的数组中没有零开头。但是因为它是一个int[]，在删除重复项后，剩余的索引将被填充0。这就是为什么您可以在数组中看到很多零的原因。要摆脱那些 0，您需要创建另一个大小较小的数组（大小应该等于您在数组中的唯一数字的数量，不包括 0）。

如果您可以对数组进行排序（我看到它已经排序），那么您可以将所有零放在前面或将它们推到最后。基于此，您可以迭代数组并从数组中实际值开始的位置获取索引。然后，您可以使用Arrays.copyOfRange(array, from, to)仅包含所需元素的数组来创建副本。

于 2013-10-04T06:51:33.070 回答
0

尝试这个

 package naveed.workingfiles;



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, };
        removeDups(a);
    }

private static void removeDups(int[] a) {
    int[] result = new int[a.length];
    int j = 0;
    int count = 0;
    for (int i : a) {
        if (!isExist(result, i)) {
            result[j++] = i;
            count++;
        }
    }
    System.out.println(count + "_____________");
    for (int i=0;i<count;i++) {
        System.out.println(result[i]);
    }

    // return result;
}

private static boolean isExist(int[] result, int i) {
    for (int j : result) {
        if (j == i) {
            return true;
        }
    }
    return false;
}

}

于 2013-10-04T07:10:42.303 回答
0 
public class RemoveDups {
    public static void main(String[] args) {
        int[] a = { 1, 2, 0, 3, 1,0, 3, 6, 2};
        removeDups(a);
    }

private static void removeDups(int[] a) {
    int[] result = new int[a.length];
    int j = 0;
    int count = 0;
    boolean zeroExist = false;
    for (int i : a) {
        if(i==0 && !zeroExist){
            result[j++] = i;
            zeroExist = true;
            count++;
        }
        if (!isExist(result, i)) {
            result[j++] = i;
            count++;
        }
    }
    System.out.println(count + "_____________");
    for (int i=0;i<count;i++) {
        System.out.println(result[i]);
    }

    // return result;
}

private static boolean isExist(int[] result, int i) {

    for (int j : result) {
        if (j == i) {
            return true;
        }
    }
    return false;
}
}
// It works even Array contains 'Zero'
于 2017-05-02T11:26:03.437 回答
-1 
class Lab2 {
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 };
    removeDups(a);
}

private static void removeDups(int[] a) {
    int[] result = new int[a.length];
    int j = 0;
    int count = 0;
    for (int i : a) {
        if (!isExist(result, i)) {
            result[j++] = i;
            count++;
        }
    }
    System.out.println(count + "_____________");
    for (int i = 0; i < count; i++) {
        System.out.println(result[i]);
    }
}

private static boolean isExist(int[] result, int i) {
    for (int j : result) {
        if (j == i) {
            return true;
        }
    }
    return false;
}
}
于 2015-09-04T13:45:22.660 回答