用O（nlogn）时间O（1）空间有效地计算数组中的等值对的数量-Java 学习之路

给定 int 值的数组：

{4, 2, 6, 5, 4, 4, 5}

合格对的索引是

{0, 4}
{0, 5}
{4, 5}
{3, 6}

第二个指数应该大于第一个指数 . 所以正确的结果是4 .

请注意，最坏情况下的时间复杂度为O（nlogn），最坏情况下的空间复杂度为O（1） .

天真的解决方案：两个循环，但O（n ^ 2） .

我的解决方案：快速排序数组，然后变成 {2, 4, 4, 4, 5, 5, 6} ，计算元素数量，如果它出现多次：例如：4的数量是3，计数= 3 * 2/2 = 3，数字5是2， count = 2 * 1/2 = 1 .

我的解决方案的问题：最坏情况可以有O（n ^ 2），但它需要O（1）空间，所以我没有选择合并排序 .

谁能帮忙提供一个好的解决方案？谢谢 .

2 回答

1
我能想到的最简单的代码是使用Set：
```
int duplicateCount = 0;
Set<Integer> set = new HashSet<>();
for (int n : numbers)
    if (!set.add(n))
        duplicateCount++;
```
或者java 8：
```
Set<Integer> set = new HashSet<>();
int dups = Arrays.stream(numbers).filter(n -> !set.add(n)).count();
```
如果添加更改了集合（即它是一个新数字），Set的add（）方法返回true，否则返回false（即它是重复的） .

HashSet具有出色的性能 - O（1） - 并且算法是O（n）性能和（取决于分布）<O（n）空间 .

如果你真的需要O（1）空间，你可以使用Arrays.sort(int[])对数组进行排序（它在Java 7中的实现使用Dual-Pivot Quicksort，这是一个就地 - 即O（1） - 算法）然后添加此代码：
```
Arrays.sort(numbers);
int dups = 0;
for (int i = 1; i < numbers.length; i++)
    if (numbers[i] = numbers[i - 1])
        dups++;
```
Arrays.sort() 非常有效O（nlogn）并且没有使用O（1）的额外空间 .
回复于 2024-04-29T04:27:10+08:00

应该是吗？

private static int GetCount(int count)
    {
        if(count == 0)
        {
            return 0;
        }
        return (count + 1) * count / 2;
    }

    public static int solution1(int[] a)
    {
        Array.Sort(a);
        int count = 0;
        int currentCount = 0;
        for (int i = 1; i < a.Length; i++)
        {
            if (a[i - 1] == a[i])
            {
                currentCount++;
            }
            else
            {
                count += GetCount(currentCount);
                currentCount = 0;
            }
        }
        count += GetCount(currentCount);
        return count;
    }

回复于 2024-04-29T04:27:10+08:00

用O（nlogn）时间O（1）空间有效地计算数组中的等值对的数量

2 回答

相关问题