java - 使用 HashMap 的稀疏数组

Question

稀疏数组

有一个输入字符串的集合和一个查询字符串的集合。对于每个查询字符串，确定它在输入字符串列表中出现的次数。例如，给定输入字符串=['ab','ab','abc']和查询=['ab','abc','bc']，我们找到 2 个 'ab' 实例，1 个 'ab' 实例和 0 的 'bc'。对于每个查询，我们将一个元素添加到返回数组中， result=[2,1,0] 。

https://www.hackerrank.com/challenges/sparse-arrays/problem?isFullScreen=true

我尝试了这个解决方案，但它只通过了 3 个测试用例。

static int[] matchingStrings(String[] strings, String[] queries) {
        int[] result_arr=new int[queries.length];
        HashMap<String,Integer> map=new HashMap<>();
        for(int i=0;i<queries.length;i++)
        {
            map.put(queries[i],i);
        }
        for(int i=0;i<strings.length;i++)
        {
            if(map.containsKey(strings[i]))
            {
                int index=map.get(strings[i]);
                System.out.println(index);
                result_arr[index]+=1;
            }
        }
        return result_arr;
    }

Answer 1

如果您的查询数组具有重复值，它将中断。

因此，您应该为 strings 数组创建 HashMap ，而不是创建 queries 数组的 HashMap 。这是因为对于每个查询，您需要检查该字符串在 strings 数组中出现的次数。目前，如果您的查询数组中存在重复值，您的 HashMap 本身将无法正确填充。

这是更新后的代码:

static int[] matchingStrings(String[] strings, String[] queries) {
        int[] result_arr=new int[queries.length];
        HashMap<String,Integer> map=new HashMap<>();
        for(int i=0;i<strings.length;i++)
        {
            if(map.containsKey(strings[i])) {
                map.put(strings[i], map.get(strings[i])+1);
            } else {
                map.put(strings[i],1);
            }
        } 
        for(int i=0;i<queries.length;i++)
        {
            if(map.containsKey(queries[i]))
            {
                result_arr[i]+=map.get(queries[i]);
            }
        }
        return result_arr;

    }