使用大小为 30K 的数组进行测试时，使用 HashMap 实现的代码失败

Question

我正在努力解决下面链接中的代码挑战，但在第 13 到 19 种情况下失败了。我读到 HashMap 可以获取大量数据，但我的解决方案似乎不适用于数组（杂志）为30K。以下是我实施的解决方案。我用 4K 数组测试了代码，效果很好static void checkMagazine(String[] magazine, String[] note) {    int initSize_m = (int) Math.ceil(magazine.length / 0.75);    int initSize_n = (int) Math.ceil(note.length / 0.75);    HashMap<Integer, String> m_hash= new HashMap<Integer, String>(initSize_m);    HashMap<Integer, String> n_hash= new HashMap<Integer, String>(initSize_n);    for(int i= 0; i < note.length; i++){      n_hash.put(i, note[i]);    }    for(int i= 0; i < magazine.length; i++){      m_hash.put(i, magazine[i]);    }    boolean flag=true;    if(note.length<magazine.length){    for (Map.Entry<Integer, String> entry : n_hash.entrySet()) {        flag = m_hash.containsValue(entry.getValue());        if(flag){            m_hash.values().removeIf(v -> v.equals(entry.getValue()));        }else{            break;        }    }    }else{    for (Map.Entry<Integer, String> entry : m_hash.entrySet()) {        flag = n_hash.containsValue(entry.getValue());        if(flag){            n_hash.values().removeIf(v -> v.equals(entry.getValue()));        }else{            break;        }    }    }    if(flag){        System.out.println("Yes");    }else{        System.out.print("No");    }}案例13至19失败

Answer 1

您的地图应该将单词作为键，将它们的计数作为值。按单词在输入中的位置映射单词并不能帮助您找到它们。

Mapa （也称为）的全部要点Dictionary是能够通过给定键快速查找值。在这种情况下，HashMap操作是 O(1)，而通过迭代所有条目值（如您的情况）来查找值要慢得多 -> O(n)。我强烈建议您阅读有关地图和集合的内容。

这是一个正确的解决方案：

public class HackerRank {

    public static void main(String[] args) {

        final Scanner in = new Scanner(System.in);

        final int numberOfWordsInMagazine = in.nextInt();

        final int numberOfWordsInNote = in.nextInt();

        final Map<String, Integer> wordsInMagazine = new HashMap<>();

        for (int i = 0; i < numberOfWordsInMagazine; i++) {

            final String word = in.next();

            wordsInMagazine.merge(word, 1, Integer::sum);

        }

        boolean canPrintMessage = true;

        for (int i = 0; i < numberOfWordsInNote; i++) {

            final String word = in.next();

            Integer remainingCount = wordsInMagazine.computeIfPresent(word, (key, value) -> value - 1);

            if (null == remainingCount || remainingCount < 0) {

                canPrintMessage = false;

                break;

            }

        }

        System.out.println(canPrintMessage ? "Yes" : "No");

    }

}