在较大的测试用例中失败：最常见元素的频率

Question

问题： 元素的频率是指它在数组中出现的次数。 给定一个整数数组 nums 和一个整数 k。在一次操作中，您可以选择索引

nums

并将该索引处的元素增加 1。

执行最多 k 次操作后返回元素的最大可能频率。

我的解决方案：

class Solution {
public:
    
    static bool greater(int a,int b){ return b<a;}
    int maxFrequency(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end(),greater);
        int max = nums[0];
        int cnt=1;
        for(int i =1;i<nums.size();i++){
            if(nums[i] == max){
                cnt++;
            }
            int diff =max-nums[i];
            if( diff<= k){
                cnt++;
                k -= diff;
            }else{
                return cnt;
            }
        }
        return cnt;
    }
};

适用于：

Input: nums = [1,2,4], k = 5
Output: 3
Explanation: Increment the first element three times and the 
second element two times to make nums = [4,4,4]. 4 has a frequency of 3

但在以下测试用例中失败：

nums = [9930,9923,9983,9997,9934,9952,9945,9914,9985,9982,9970,9932,9985,9902,9975,9990,9922,9990,9994,9937,9996,9964,9943,9963,9911,9925,9935,9945,9933,9916,9930,9938,10000,9916,9911,9959,9957,9907,9913,9916,9993,9930,9975,9924,9988,9923,9910,9925,9977,9981,9927,9930,9927,9925,9923,9904,9928,9928,9986,9903,9985,9954,9938,9911,9952,9974,9926,9920,9972,9983,9973,9917,9995,9973,9977,9947,9936,9975,9954,9932,9964,9972,9935,9946,9966]

k = 3056

Answer 1

对于 C++，我期望这样的代码：

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>

// do not use `using namespace std` one of the things leetcode does by default ):

// pass vector by const & to avoid copy and modification
int find_most_common_element(const std::vector<int>& values)
{
    // https://en.cppreference.com/w/cpp/container/unordered_map
    std::unordered_map<int,std::size_t> histogram;

    // one liner to build of the histogram
    // if a key does not exist a new entry with value 0 is made
    // then entry (count) is increased by one
    for(const auto value : values) histogram[value]++;

    // find the element with the highest count
    // use lambda expression to customize the find function
    auto it = std::max_element(histogram.begin(),histogram.end(),[](const auto& lhs, const auto& rhs)
    {
        const auto& lhs_count = lhs.second;
        const auto& rhs_count = rhs.second;
        return (lhs_count < rhs_count);
    });

    // structured binding (to show you *it points to a key/value pair from unordered_map)
    const auto& [value,count] = *it;
    return value;
}

int main()
{
    std::vector<int> values {9930,9923,9983,9997,9934,9952,9945,9914,9985,9982,9970,9932,9985,9902,9975,9990,9922,9990,9994,9937,9996,9964,9943,9963,9911,9925,9935,9945,9933,9916,9930,9938,10000,9916,9911,9959,9957,9907,9913,9916,9993,9930,9975,9924,9988,9923,9910,9925,9977,9981,9927,9930,9927,9925,9923,9904,9928,9928,9986,9903,9985,9954,9938,9911,9952,9974,9926,9920,9972,9983,9973,9917,9995,9973,9977,9947,9936,9975,9954,9932,9964,9972,9935,9946,9966};
    std::cout << find_most_common_element(values);
    return 0;
}

Answer 2

您的算法的问题在于它假设最大的元素将是最频繁的元素；但事实并非如此。

要了解原因，请考虑 k = 1 时的 [1,2,100]。您可以通过增加 1（给出 [2,2,100]）来获得频率为 2 的元素，但您的算法甚至不会尝试这样做。

就此而言，请考虑 k = 1 的 [1,1,100]。您从一开始就有一个频率为 2 的元素，但您的算法会忽略它，因为它不是最大值，并返回 1。