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

Question

我正在努力解决下面链接中的代码挑战，但在案例 13 到 19 中失败了。我读到 HashMap 可以获取大量数据，但我的解决方案似乎不适用于数组(杂志)为 30K 的情况。

下面是我实现的解决方案。

感谢帮助。

https://www.hackerrank.com/challenges/ctci-ransom-note/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps

我用 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

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

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

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

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");
    }
}