Java +从int数组中计算重复项而不使用任何集合或另一个中间数组

2022-01-10 00:00:00 arrays duplicates collections java

作为 Java 面试题的一部分，我有以下问题需要解决.但我有点想知道如果没有任何 Collection 或中间数组，我该如何实现它.

As a part of the Java interview question paper I have got following issue to solve. But I am bit wonder whether how can I implement it without any Collection or intermediate Array.

问题:- 在不使用任何集合或其他中间数组的情况下计算 int 数组中的重复项

Question:- Count duplicates from int array without using any Collection or another intermediate Array 

Input values:- {7,2,6,1,4,7,4,5,4,7,7,3, 1}  

Output:- Number of duplicates values: 3
         Duplicates values: 7, 4, 1

我已经实施了以下解决方案，但尚未完成.有人有什么想法吗?谢谢.

I have implemented following solution but was not completed one. Any one has some idea? Thanks.

public static void duplicate(int numbers[]) {

    for (int i = 0; i < numbers.length; i++) {

        boolean duplicate = false;
        int j = 0;

        while (j < i){

            if ((i != j) && numbers[i] == numbers[j]) {
                duplicate = true;
            }

            j++;
        }

        if (duplicate) {
            System.out.print(numbers[i] + " ");
        }
    }
}

推荐答案

解决这个问题的最简单方法是先对数组进行排序，然后在遇到重复项时遍历数组:

The easiest way to solve this problem is to sort the array first, and then just walk through the array counting duplicates as you encounter them:

int[] numbers = new int[]{7,2,6,1,4,7,4,5,4,7,7,3,1};
int temp = 0;

// I chose to do a bubble sort of the array,
// but you are free to use any method you wish (e.g. Arrays.sort)
System.out.print("Duplicates values: ");
for (int i=0; i < numbers.length; ++i) {
    for (int j=1; j < (numbers.length - i); ++j) {
        if (numbers[j-1] > numbers[j]) {
            temp = numbers[j-1];
            numbers[j-1] = numbers[j];
            numbers[j] = temp;
        }
    }
}


// walk through the sorted array and count duplicates
int numDup = 0, dupCount = 0;
int previous = -1;
for (int i=0; i < numbers.length; ++i) {
    if (numbers[i] == previous) {
        ++numDup;
        if (numDup == 1) {
            ++dupCount;
            if (dupCount == 1) {
                System.out.print(numbers[i]);
            }
            else {
                System.out.print(", " + numbers[i]);
            }
        }
    }
    else {
        previous = numbers[i];
        numDup = 0;
    }
}

System.out.println("
Number of duplicates values: " + dupCount);

输出:

Duplicates values: 1, 4, 7
Number of duplicates values: 3

请注意，我的输出顺序与您的输出顺序相反，因为您需要通读整个数组才能知道总共有多少重复项.另外，我要指出，这个解决方案使用的唯一状态是输入数组本身，加上几个 int 变量.

Note that my output order is reverse of what you have, because you need to read through the entire array before you know how many total duplicates you have. Also, I will point out that the only state this solution uses is the input array itself, plus a couple of int varibles here and there.

此代码已在 IntelliJ 中进行了测试，并且可以正常工作.

This code has been tested in IntelliJ and it works correctly.

相关文章