Finding Duplicate numbers in a sorted Array-CodePudding

I want to know if there is a any way to find out how many pairs is in a sorted array The easiest way is using two for loop

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

But the point is this two for loops works even in unsorted array if our array is sorted is there any way to find the pairs with only one for or while loop? example can be {1, 1, 1, 2, 3, 3} it have 4 pairs [0][1], [0][2], [1][2], [4][5]

CodePudding user response：

Well, you don't have to compare every element with every other (what 2 nested for-loops do), but only the neighbouring ones...

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

Note that for-loop only runs up to the n - 1 element, otherwise there will be a null-pointer exeption

CodePudding user response：

Try this.

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

output: