如何在不使用集合的情况下有效地从数组中删除重复项？

无需借助 Set 即可高效地从数组中删除重复项

您已努力创建一个自定义解决方案来从数组中删除重复元素，但性能瓶颈已经出现。为了优化此实现，我们将分析您的方法的缺点并提出替代策略。

分析您的算法

您的算法尝试通过比较每个值来搜索重复项元素与每个后续元素。这种详尽的比较导致时间复杂度为 O(n^2)。对于大型数组，此策略可能变得极其低效。

优化方法

为了显着提高性能，我们可以考虑以下优化：

1. 利用哈希映射：实现哈希映射来存储迭代过程中遇到的唯一元素。将每个元素添加到数组时，检查它是否已作为哈希映射中的键存在。如果没有，请添加。这种方法可以实现高效的恒定时间查找操作，将时间复杂度降低到 O(n)。
2. 过滤前排序： 按升序对数组进行排序。现在，重复的元素将彼此相邻。迭代已排序的数组并消除相邻的重复项，从而得到线性时间 O(n) 算法。

替代解决方案

虽然上述优化可以为了提高算法的性能，您还可以考虑其他已建立的技术：

• 设置集合：由于您需要避免使用 Set，因此我们不会深入研究此选项。
• 使用排序集合：与过滤前排序类似，利用排序集合，例如TreeSet 或 NavigableSet。它自动维护排序顺序并允许高效的元素检索，从而导致 O(n log n) 复杂度。

实现

基于优化方法，使用哈希映射的算法的修改版本可能是：

public static int[] removeDuplicatesWithoutSet(int[] arr) {

    HashMap<Integer, Boolean> map = new HashMap<>();
    int end = arr.length;

    for (int i = 0; i < end; i++) {
        if (map.containsKey(arr[i])) {
            int shiftLeft = i;
            for (int k = i + 1; k < end; k++, shiftLeft++) {
                arr[shiftLeft] = arr[k];
            }
            end--;
            i--;
        } else {
            map.put(arr[i], true);
        }
    }

    int[] whitelist = new int[end];
    for (int i = 0; i < end; i++) {
        whitelist[i] = arr[i];
    }
    return whitelist;
}

以上是如何在不使用集合的情况下有效地从数组中删除重复项？的详细内容。更多信息请关注PHP中文网其他相关文章！