在排序数组中查找重复数字

Question

我想知道是否有任何方法可以找出排序数组中有多少对最简单的方法是使用两个 for 循环

 for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] == arr[j])

但重点是这两个 for 循环即使在未排序的数组中也能正常工作如果我们的数组已排序，是否有任何方法可以找到只有一个 for 或 while 循环的对？例子可以是 {1, 1, 1, 2, 3, 3} 它有 4 对 [0][1], [0][2], [1][2], [4][5]

Answer 1

好吧，您不必将每个元素相互比较（2 个嵌套的 for 循环所做的），而只需比较相邻的元素...

int paires = 0;
for(int i = 0; i < arr.lenght - 1; i++) {
   if(arr[i] == arr[i + 1]) paires++; // Test if the i-th element is equal to the i+1-th element and increasing counter if so.
}

注意for循环只能运行到第n - 1个元素，否则会出现空指针异常

Answer 2

试试这个。

static int combination(int start, int end) {
    int size = end - start;
    return size * (size - 1) / 2;
}

static int countDuplicatedNumberPairs(int[] arr) {
    int length = arr.length, count = 0;
    if (length <= 0) return count;
    int start = 0, previous = arr[0];
    for (int i = 1; i < length; ++i)
        if (arr[i] != previous) {
            count += combination(start, i);
            start = i;
            previous = arr[i];
        }
    count += combination(start, length);
    return count;
}

public static void main(String[] args) {
    int[] arr =  {1, 1, 1, 2, 3, 3} ;
    System.out.println(countDuplicatedNumberPairs(arr));
}

输出：

Answer 3

好吧，你需要遍历数组并计算连续相同的数字。如果遇到不同的数字，则需要计算最后看到的数字的对数。对于每个不同的号码，您都需要这样做。

在下图中，您看到有三个 子序列 具有相同的数字。

     a      b    c
  ┌──┴──┐  ┌┴─┐  │
  │     │  │  │  │
[ 1, 1, 1, 2, 2, 3 ]

让我们首先定义一个方法来计算特定计数的对数。它的公式总是

⠀⠀⠀⠀⠀⠀² -
()⠀=⠀──────
⠀⠀⠀⠀⠀⠀⠀⠀2

int countPairs(int number) {
    return number * (number - 1) / 2;
}

那我们来写遍历数组的方法吧。我在代码中添加了注释来解释发生了什么：

int countPairs(int[] array) {
    // If our array is empty or contains a single element, then there are no
    // pairs, obviously
    if (array.length < 2) {
        return 0;
    }

    // We keep track of the total number of pairs here
    int totalPairs = 0;

    // We also keep track of the number of consecutive identical numbers.
    int consecutive = 1;

    // We begin our index with 1, since we need to compare it to the previous one
    // (and we don't want an ArrayIndexOutOfBoundsException to be thrown)
    for (int i = 1; i < array.length; i++) {
        if (array[i] == array[i - 1]) {
            // If the encountered number is the same as the previous one,
            // then increment the subsequence counter
            consecutive++;
        }
        else {
            // If the number is different than the previous one, then a new subsequence
            // has started. We need to process the previous subsequence. Calculate the
            // number of pairs, add it to the result, and then reset `consecutive`
            totalPairs += countPairs(consecutive);
            consecutive = 1;
        }
    }
    // At last, process the last sequence
    totalPairs += countPairs(consecutive);
    return totalPairs;

在排序数组中查找重复数字

Finding Duplicate numbers in a sorted Array

java

arrays

for-loop

while-loop