java - 打印出数组中出现次数最少的元素

Question

好的，所以我几天前发现了这个问题，但它被搁置了，不允许我在上面发布任何内容。

***注意:数组中的值或顺序是完全随机的。它们也应该可以是负数。

有人推荐了这段代码并为它点赞，但我看不出这能如何解决问题。如果出现次数最少的元素之一不在数组的开头，则这不起作用。这是因为 maxCount 将等于 array.length 并且结果数组将始终采用下面编写的代码中的第一个元素。

使用如下简单的 java 有什么方法可以解决这个问题？没有 HashMap 和诸如此类的东西。我已经考虑了一段时间，但真的想不出来任何东西。也许使用双数组来存储某个数字的计数？你会如何解决这个问题？有什么指导吗？

public static void main(String[] args)
{
    int[] array = { 1, 2, 3, 3, 2, 2, 4, 4, 5, 4 };
    int count = 0;
    int maxCount = 10;
    int[] results = new int[array.length];
    int k = 0; // To keep index in 'results'

    // Initializing 'results', so when printing, elements that -1 are not part of the result
    // If your array also contains negative numbers, change '-1' to another more appropriate
    for (int i = 0; i < results.length; i++) {
        results[i] = -1;
    }

    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array.length; j++) {
            if (array[j] == array[i]) {
                count++;
            }
        }

        if (count <= maxCount) { // <= so it admits number with the SAME number of occurrences
            maxCount = count;
            results[k++] = array[i]; // Add to 'results' and increase counter 'k'
        }
        count = 0; // Reset 'count'
    }

    // Printing result
    for (int i : results) {
        if (i != -1) {
            System.out.println("Element: " + i + ", Number of occurences: " + maxCount);
        }
    }
}

归功于:https://stackoverflow.com/users/2670792/christian对于代码

我不能竖起大拇指，所以我想在这里说声谢谢所有回答的人。

Answer 1

您还可以使用面向对象的方法。

首先创建一个类Pair:

class Pair {
    int val;
    int occ;

    public Pair(int val){
        this.val = val;
        this.occ = 1;
    }

    public void increaseOcc(){
        occ++;
    }

    @Override
    public String toString(){
        return this.val+"-"+this.occ;
    }
}

现在主要是:

public static void main(String[] args)  {
    int[] array = { 1,1, 2, 3, 3, 2, 2, 6, 4, 4, 4 ,0};
    Arrays.sort(array);

    int currentMin = Integer.MAX_VALUE;
    int index = 0;
    Pair[] minOcc = new Pair[array.length];
    minOcc[index] = new Pair(array[0]);

    for(int i = 1; i < array.length; i++){
        if(array[i-1] == array[i]){
            minOcc[index].increaseOcc();
        } else {
            currentMin = currentMin > minOcc[index].occ ? minOcc[index].occ : currentMin;
            minOcc[++index] = new Pair(array[i]);
        }
    }

    for(Pair p : minOcc){
        if(p != null && p.occ == currentMin){
            System.out.println(p);
        }
    }

}

哪些输出:

0-1
6-1

解释:

首先，您对值数组进行排序。现在你遍历它。

虽然当前值等于前一个值，但您增加了该值的出现次数。否则表示当前值不同。因此，在本例中，您创建了一个具有新值和一次出现的新 Pair。

在迭代期间，您将跟踪您看到的最少出现次数。

现在您可以遍历 Pair 数组并检查每个 Pair 的出现值是否等于您找到的最小出现次数。

此算法在 O(nlogn) 中运行(由于 Arrays.sort)，而不是您之前版本的 O(n²)。