黑客排名频率查询

Question

我正在做黑客排名频率查询问题，我的所有测试用例都通过了，但有一个超过了时间限制。我该怎么做才能使我的程序更有效率。

static List<Integer> freqQuery(List<List<Integer>> queries) {
    List<Integer> freqCount = new ArrayList();
    HashMap<Integer, Integer> data = new HashMap<>();
    
    for(List q : queries){
        int op = (Integer)q.get(0);
        int num = (Integer)q.get(1);
        
        switch (op){
            case 1:
                if(data.get(num) == null){
                    //Add new value to hashmap
                    data.put(num, 1);
                }else{
                    data.put(num, data.get(num) + 1);
                }
            break;
            case 2:
                if(data.get(num) != null){
                    if(data.get(num) == 0){
                        //data.remove(num);
                    }else{
                       data.put(num, data.get(num) - 1); 
                    }
                }
            break;
            case 3:
                if(data.containsValue(num)){
                    freqCount.add(1);
                }else{
                    freqCount.add(0);
                }
            break;
        }

    }
    
    return freqCount;
}

Answer 1

classboolean containsValue(Object value)HashMap<K,V>的time complexity为O(n)。 如果在 case 3 中，您可以进行恒定时间查找 - O(1)，您的代码将非常高效。

根据问题陈述中提到的约束：

最大查询数：

1 <= q <= 10^5
x、y 和 z 的最大可能值：

1 <= x, y, z <= 10^9

为了检查您的数据结构中是否存在频率恰好为 z in O(1) 的整数，你可以使用一个简单的数组.

如果数组中的索引 z 处有一个元素 e，则表示数据结构中有 e 个元素 frequency z .数组的 index 表示 frequency 和该索引处的 value 表示 数据结构中具有该频率的元素数量。您可以将此数组称为 nestedFrequency，因为它存储 频率的频率 。数组的 size 将是 100001。 由于最大可能查询数为100000，所以不能有频率大于100000的元素。

伪代码：

for i = 1 to queries.length
    int choice = queries[i][0]
    int number = queries[i][1]
    
    switch (choice)
        case 1:
            Add the number in hashMap and map it to a value of 0 if not already 
            present.

            //Obtain the previous frequency of that number in hashMap
            int oldFre = hashMap.get(number)
            
            //Update the nested frequency array
            nestedFrequency[oldFre]--
            nestedFrequency[oldFre+1]++

            //Update the frequency of that number in hashmap
            Increase the frequency of that number in hashMap 
        case 2:
            if there is a mapping present of the given number in hashMap
                //Obtain the previous frequency of that number in hashMap
                int oldFre = hashMap.get(number)

                //Update the nested frequency array
                nestedFrequency[oldFre]--
                if (oldFre-1 != 0) nestedFrequency[oldFre-1]++
                
                //Update the frequency of that number in hashmap
                if (oldFre-1 == 0) remove the mapping of that element in hashmap
                else decrease its old frequency
        case 3:
            if number < 100001 and nestedFrequncy[number] > 0
                print 1
            else 
                print 0

希望对您有所帮助。 对任何进一步的问题发表评论。

黑客排名频率查询

Hacker Rank Frequency Queries

java

algorithm

hashmap