java - 以最小时间复杂度查找数组中最大重复整数的总和

Question

我是编程新手，正在尝试通过探索来学习。我一直在寻找一种解决方案，以找到具有最佳时间复杂度的数组中最大时间重复整数的总和。假设我们有 [1, 2, 3, 3] 结果应该是 6，时间复杂度最小，比如 O(n)。

我想出了一个解决方案，但不确定其复杂性。需要一些帮助来理解下面提到的代码是否具有最小的复杂性或者它可以更好(绝对!)。抱歉，如果我有任何错误，请提前致谢。

public static int mapBasedFinder(int[] arr){
    Map<Integer, Integer> values = new HashMap<Integer, Integer>();
    int result = 0;
    for(int i=0; i<arr.length; i++){
        int temp = arr[i];
        if(values.containsKey(temp))
            values.put(temp, values.get(temp)+1);
        else
            values.put(temp, 1);

        Map.Entry<Integer, Integer> maxEntry = null;
        for (Map.Entry<Integer, Integer> entry : values.entrySet())
        {
            int key = entry.getKey();
            if (maxEntry == null || entry.getValue().compareTo(maxEntry.getValue()) > 0)
            {
                maxEntry = entry;
                result = entry.getValue() * key;
            }
        }
    }
    return result;
}

Answer 1

您有两个循环，第二个循环在第一个循环中。这会给你带来比 O(n) 更糟糕的复杂性 - 可能是 O(n²)(最坏情况)。

但它看起来是一个错误。您应该将第二个循环移到第一个循环之外，因为您只需要在完全遍历数组一次后检查最大值，以找出每个数字重复了多少次。

然后你的复杂性又回到了 O(n)，因为没有 O(2n) 这样的东西——迭代两次值仍然是 O(n)。