时间戳

首页 > 解决方案 > Hackerrank：频率查询问题出现超时错误，如何进一步优化代码？

java - Hackerrank：频率查询问题出现超时错误，如何进一步优化代码？

问题描述

我在java 8中使用hashmap函数编写的代码出现超时错误。当我提交答案时，由于hackerrank平台上的14个测试用例中有5个测试用例超时错误而失败。

下面是问题

您会收到查询。每个查询都是下面描述的两个整数的形式：

  1. x : 在你的数据结构中插入 x。
  2. y ：从数据结构中删除一次出现的 y（如果存在）。
  3. z ：检查是否存在任何频率恰好为 z 的整数。如果是，则打印 1，否则打印 0。

查询以二维数组的形式给出，其中查询[i][0] 包含操作，查询[i][1] 包含数据元素。

我应该如何进一步优化这段代码？

static HashMap<Integer,Integer> buffer = new HashMap<Integer,Integer>();

          // Complete the freqQuery function below.
        static List<Integer> freqQuery(List<List<Integer>> queries) {



        List<Integer> output = new ArrayList<>();


        output = queries.stream().map(query -> {return performQuery(query);}).filter(v -> v!=-1).collect(Collectors.toList()); 
        //get the output array iterate over each query and perform operation


        return output;

        }

        private static Integer performQuery(List<Integer> query) {

            if(query.get(0) == 1){
                buffer.put(query.get(1), buffer.getOrDefault(query.get(1), 0) + 1);
            }
            else if(query.get(0) == 2){
                if(buffer.containsKey(query.get(1)) && buffer.get(query.get(1))>0 ){
                    buffer.put(query.get(1), buffer.get(query.get(1)) - 1);
                }
            }
            else{
                if(buffer.containsValue(query.get(1))){
                    return 1;
                }
                else{
                    return 0;
                }
            }
            return -1;
        }



        public static void main(String[] args) {


            List<List<Integer>> queries =  Arrays.asList(
                                            Arrays.asList(1,5),
                                            Arrays.asList(1,6),
                                            Arrays.asList(3,2),
                                            Arrays.asList(1,10),
                                            Arrays.asList(1,10),
                                            Arrays.asList(1,6),
                                            Arrays.asList(2,5),
                                            Arrays.asList(3,2)
                                            );
          long start = System.currentTimeMillis();

            System.out.println(freqQuery(queries));


            long end = System.currentTimeMillis();
               //finding the time difference and converting it into seconds
                  float sec = (end - start) / 1000F;
                  System.out.println("FreqQuery function Took "+sec + " s");
    }
    }

标签： java

解决方案

您的代码的问题是z操作。具体来说，该方法containsValue具有线性时间复杂度，使得算法的整体复杂度在O(n*n). 这是一个提示：在您拥有的哈希映射之上添加另一个哈希映射，该哈希映射按另一个映射的值计算出现次数。这样，您可以通过值直接查询第二个（因为在这种情况下它将是键）。

推荐阅读