今日头条java面试题之 - 编程篇

题目描述：输出数组中相差为给定值的数对个数，重复的一对只算一次。 输入： 第一行输入整数n和k，（n在[1，1000000]，k在[0，100]）； 第二行输入n个正整数。 输出： 整数，表示求出的数对个数

例1： 输入：

4 0 
1 1 1 1 

输出：1

例2： 输入：

5 2
1 3 3 2 5

输出：2

代码：

import java.util.Scanner;

public class Main {

    private static int count(int[] array, int k) {
        int count = 0;
        int size = array.length;
        if (size == 1)
            return 0;
        for (int i = 0; i < size - 1; i++) {
            if (array[i] == array[i + 1]) {
                i = tail(array, i + 1);
                if (k == 0) { // k = 0时，重复的一组元素算一对
                    count++;
                    continue;
                }
            }
            for (int j = i + 1; j < size; j++) {
                if (j != size - 1 && array[j] == array[j + 1])
                    j = tail(array, j + 1);
                if (array[i] + k == array[j]) {
                    count++;
                }
            }
        }
        return count;

    }

    // 定位到连续重复元素的末尾
    private static int tail(int[] array, int index) {
        int i = index;
        for (; i < array.length; i++) {
            if (array[i] != array[i - 1])
                return i - 1;
        }
        return array.length - 1;
    }

    // 插入排序，从小到大
    private static void insertionSort(int[] array) {
        int temp;
        int hole;
        for (int i = 1; i < array.length; i++) {
            temp = array[i];
            for (hole = i; hole > 0 && temp < (array[hole - 1]);)
                array[hole] = array[--hole];

            array[hole] = temp;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++)
            array[i] = in.nextInt();

        insertionSort(array);
        System.out.println(count(array, k));

    }
}
————————————————
版权声明：本文为CSDN博主「Harold Gao」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_40255793/article/details/79682243