时间戳

首页 > 解决方案 > 在具有大值的排序数组中查找对

java - 在具有大值的排序数组中查找对

问题描述

我目前遇到一个问题，即在具有大值的排序数组中查找对。示例：如果我将数组 sortedarr=[1, 2, 2, 2, 2, 2, 2, 3] 作为输入。它应该返回对 = 15。

我编写了下面的代码，它在 O(N2) 中适用于未排序和排序的数组。但是代码非常基本，我希望它能够在更快的时间内管理排序数组。我想最简单的方法是将当前元素与它旁边的元素进行比较。但我不知道我该怎么做。我如何设法更改代码以使其满足我的要求？

    public static int countpairs(int[] sortedarr) {
        int N = sortedarr.length;
        int pairs = 0;

        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if (sortedarr[i] == sortedarr[j]) {
                    pairs++;
                }
            }
        }
        return pairs;
    }
}

标签： javaarrays

解决方案

这是在 O(N) 而不是 O(N^2) 中执行此操作的一种方法：

public static void main(String[] args) {
    int[] a= new int[] {1, 2, 2, 2, 2, 2, 2, 3};
    int i = 0;
    int n = a.length;
    int ans = 0;
    while(i < n - 1) {
        int dupeCount = 1;
        while(i < n - 1 && a[i] == a[i + 1]) {
            dupeCount++;
            i++;
        }
        if(dupeCount > 1) {
            ans = ans + (dupeCount * (dupeCount-1) / 2);
        }
        i++;
    }
    System.out.println(ans);
}

产出 15。

这个想法有点类似于冒泡排序使用的。我们只需要查看数组中的每一项及其后继项，看看它是否重复。从那里，可以创建的不同对的数量仅为C(dupeCount,2) = dupeCount * (dupeCount - 1) / 2. 我们将所有此类事件相加得到最终答案。

推荐阅读