使用大小为 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 {&nbsp; &nbsp; public static void main(String[] args) {&nbsp; &nbsp; &nbsp; &nbsp; final Scanner in = new Scanner(System.in);&nbsp; &nbsp; &nbsp; &nbsp; final int numberOfWordsInMagazine = in.nextInt();&nbsp; &nbsp; &nbsp; &nbsp; final int numberOfWordsInNote = in.nextInt();&nbsp; &nbsp; &nbsp; &nbsp; final Map<String, Integer> wordsInMagazine = new HashMap<>();&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < numberOfWordsInMagazine; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; final String word = in.next();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; wordsInMagazine.merge(word, 1, Integer::sum);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; boolean canPrintMessage = true;&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < numberOfWordsInNote; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; final String word = in.next();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Integer remainingCount = wordsInMagazine.computeIfPresent(word, (key, value) -> value - 1);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (null == remainingCount || remainingCount < 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; canPrintMessage = false;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(canPrintMessage ? "Yes" : "No");&nbsp; &nbsp; }}