在列表中查找频率差异元素

Question

实际上我正在尝试解决这个问题hackerrank Missing Numbers

让我为它添加一些描述，实际上有两个数字列表，几乎相同，但因为第一个列表中有一些遗漏，所以第二个列表包含所有完整的数字，而第一个列表缺少其中的一些数字，我们只需打印出第一个列表中丢失的数字。

问题陈述

Numeros，艺术家，拥有两个列表A和B，其中B是A的排列。 Numeros非常自豪这些列表。 不幸的是，在从一个展览到另一个展览的运输过程中，A中的一些数字被遗漏了。你能找到缺失的数字吗？

注意事项

如果数字在列表中出现多次，则必须确保两个列表中该数字的频率相同。 如果不是这种情况，则它也是一个丢失的数字。

您必须按升序打印所有缺失的数字。

仅打印每个缺失的数字一次，即使它丢失了多次也是如此。

B中最大和最小数字之间的差小于或等于100。

输入格式 将有四行输入：

n - the size of the first list 
This is followed by n space-separated integers that make up the first list. 
m - the size of the second list 
This is followed by m space-separated integers that make up the second list.

输出格式 按升序输出缺失的数字：

约束条件

1≤n,m≤1000010 
1≤x≤10000,x∈B 
Xmax−Xmin<101

示例输入

10
203 204 205 206 207 208 203 204 205 206
13
203 204 204 205 206 207 205 208 203 206 205 206 204

样例输出

204 205 206

我写了这段代码：-

这是代码：-

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        Map<Integer, Integer> mA = new HashMap<>(n);
        int curr = 0;
        while(n--> 0){// Creating the first map having number & its frequency
            curr = scan.nextInt();
            if(mA.containsKey(curr)){
                Integer prev = mA.get(curr);
                mA.put(curr, prev + 1);
            }else{
                mA.put(curr, 1);
            }
        }

        int n1 = scan.nextInt();
        Map<Integer, Integer> mB = new HashMap<>(n1);
        while(n1--> 0){// Creating the second map having number & its frequency
            curr = scan.nextInt();
            if(mB.containsKey(curr)){
                Integer prev = mB.get(curr);
                mB.put(curr, prev + 1);
            }else{
                mB.put(curr, 1);
            }   
        }

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

            //Problem I think is this part somewhere I am not doing it correct in this loop
            for(Map.Entry<Integer, Integer> entry : mB.entrySet()){
                Integer k = entry.getKey();
                Integer v = entry.getValue();
                if(!mA.containsKey(k)){
                   l.add(k);
                }else if(mA.get(k) != v){
                    l.add(k);
                }
            }
            Collections.sort(l);
            List<Integer> list = new ArrayList<>(new LinkedHashSet<Integer>(l));

           for(Integer i : l){
               System.out.print(i + " ");
           }
        }
}

我认为问题出在for循环中，我在比较两个map中的条目时。我觉得我没有正确的方式！！ 因为它打印了一个在两个地图中具有相同频率计数的数字。

- John Doe

---

你有什么问题？你的输出不正确吗？ - Pham Trung

是的，它正在打印一个在两个映射中具有相同频率计数的数字。 - John Doe

出奇地，我没有看到你的代码有任何问题。你是否有输入有问题？ - nitegazer2003

@JohnDoe，请帮我更新我的答案，看一下 :) - Pham Trung

是的，这也是一个不错的方法，但是我发现过度依赖集合框架往往会花费太多时间，有时会超时。 - John Doe

Answer 1

问题是：

for(Map.Entry<Integer, Integer> entry : mB.entrySet()){
    Integer k = entry.getKey();
    Integer v = entry.getValue();
    if(!mA.containsKey(k)){
        l.add(k);
    }else if(mA.get(k).intValue() != v.intValue()){//This is the problem
        l.add(k);
    }
}

因为之前你比较的是两个整数对象而不是两个int值（对于小整数值，它们都映射到同一个对象，但对于较大的值，在自动装箱时Java会创建新的对象）。

实际上，这个问题只需要一个Map，如果你使用TreeMap而不是HashMap，你会发现更加方便。

注意到Xmax - Xmin < 101，所以我们甚至可以使用一个数组data[101]来存储数字，以进一步提高性能。

- Pham Trung

---

那么唯一的问题就是这个整数对象，而不是其他任何东西？？你是如何这么快确定这个问题的？我敢打赌我自己要花几天时间才能找出来，非常感谢。如果可能，请分享更多关于这件事的信息。 - John Doe

@JohnDoe，你可以采用不同的方法，但对于你目前的方法，这就是问题的所在 :) - Pham Trung

当然，我仍在摸索中，而且我知道我的做法并不是很优雅，但我愿意尝试你提出的方法。 - John Doe

Answer 2

尝试使用数组：

int[] a = new int[n];
int[] b = new int[m];
// read into a and b
int[] freqs = new int[10001];

for (int i = 0; i < m; i++)
{
    freqs[b[i]]++;
}
for (int i = 0; i < n; i++)
{
    freqs[a[i]]--;
}
for (int i = 0; i <= 10000; i++)
{
    if (freqs[i] > 0) System.out.println(i + " ");
}

- nitegazer2003

Answer 3

  void printmissing(HashMap<Integer, Integer> firstset,HashMap<Integer, Integer> secondset){
    Set<Integer> keys=secondset.keySet();
    for(Integer k:keys){
        secondset.put(k, secondset.get(k)-firstset.get(k));
    }
    for(Integer k:keys){
        if(secondset.get(k)>0)
            System.out.print(" "+k);
    }

在主方法中添加LinkedHashMap中的整数值，并调用上述方法以按顺序显示缺失的数字。

    HashMap<Integer, Integer> firstset=new LinkedHashMap<>();
    HashMap<Integer, Integer>  secondset=new LinkedHashMap<>();

- Mohan Raj

Answer 4

试试这个

`

public class Abce{
    public static void main(String[] args) {
        ArrayList<Integer> A = new ArrayList<Integer>();
        A.add(1);
        A.add(1);
        A.add(1);
        A.add(2);
        A.add(1);

        ArrayList<Integer> B = new ArrayList<Integer>();

        B.add(1);
        B.add(1);
        B.add(2);
        B.add(1);

        //Find and remove
        for (Integer integer : B) {
            if (A.contains(integer)) {
                A.remove(integer);
            }

        }

        //Print the remaining items
        for (Integer integer : A) {
            System.out.println(integer);
        }

    }
}`

- prashant thakre

---

我还需要考虑频率。 - John Doe

如果以上操作的结果是1，那么频率已经被考虑在内。在列表A中，有1个整数出现了4次，而在列表B中，只有1个整数出现了3次。因此，结果为1，因为剩下的数字已经被移除了。实际上，我展示缺失的数字是1，因为频率不匹配。 - prashant thakre