java - 将C++映射转换为Java映射

Question

考虑下面的cpp代码

string ans = "NO";
map<int,vi> idv ; //vi is vector of int

for(int i=1;i<=n;i++)
  idv.[arr[i]].push_back(i);

//frequecy >= 3
for(auto el:idv){
   if(el.ss.size() >= 3){
      ans = "YES";}
}

//non adjecent equal elements
for(auto el:idv)
{
   if(el.ss.size() == 2 && el.ss[0] != el.ss[1]-1)
    {
      ans = "YES";
    }
}

cout<<ans<<endl;

My java translation code

                String ans = "NO";
                Map<Integer,List<Integer>> map = new HashMap<>();
                for (int i : arr) {
                    // map.merge(i,1,Integer::sum);
                    // map.put(i, )
                    List<Integer> temp = map.getOrDefault(i, new ArrayList<>());
                    temp.add(i);
                    map.put(i,temp);

                }

                //check for freq 3
                for (Map.Entry<Integer,List<Integer>> e : map.entrySet()) 
                {
                    if(e.getValue().size() == 3)     
                        ans ="YES";
                }

                //freq 2 and pos change 
                for (Map.Entry<Integer,List<Integer>> i : map.entrySet()) 
                {
                    if(i.getValue().size() == 2 && i.getValue().get(0) != i.getValue().get(1) - 1)
                        ans = "YES";    
                }

                System.out.println(ans);

Input arr[]

1 2 1
1 2 2 3 2
1 1 2
1 2 2 1
1 1 2 2 3 3 4 4 5 5

Output

YES
YES
NO
YES
NO

但是它不能正常工作。请任何人告诉我如何更有效地做到这一点。同样对于第一循环，我想我可以使用map.merge。如果有人知道该怎么做，请告诉我。
谢谢✌️

Answer 1

首先，以下代码段将索引推到 vector 的末尾，您需要在Java中使用相同的方法，而无需增强for-each循环:

// C++
for (int i=1;i<=n;i++)
    idv.[arr[i]].push_back(i);

// Java
Map<Integer, List<Integer>> map = new HashMap<>();
for (int i=0; i<arr.length; i++) {
    List<Integer> temp = map.getOrDefault(arr[i], new ArrayList<>());
    temp.add(i);
    map.put(arr[i],temp);

    // or shorter:
    // map.computeIfAbsent(arr[i], key->new ArrayList<>()).add(i);
}

接下来的事情是您在Java和C++中都对 map 进行了两次迭代，这是不必要的。使用相同的逻辑和。在Java中，您只能迭代值，如果不需要键，则无需遍历实际条目:

for (List<Integer> list: map.values()) {
    if (list.size() == 3 || (list.size() == 2 && list.get(0) != list.get(1) - 1)) {
        ans = "YES";
        break;        // no need to continue iteration, you have the answer
    }
}

利用 java-stream的优势，甚至可以简化整个过程，帮助您创建 Map<Integer, List<Integer>>:

Map<Integer, List<Integer>>  map1 = IntStream.range(0, arr.length)
    .boxed()
    .collect(Collectors.groupingBy(i -> arr[i]));

String ans = "NO";
for (List<Integer> list: map.values()){
    if (list.size() == 3 || (list.size() == 2 && list.get(0) != list.get(1) - 1)) {
        ans = "YES";
        break;
    }
}

感谢@ Holger，使用 Collectors.collectingAndThen可以更加简单:

String ans = IntStream.range(0, arr.length)
    .boxed()
    .collect(Collectors.collectingAndThen(
        Collectors.groupingBy(i -> arr[i]),
        map -> map.values().stream()
            .filter(l -> l.size() == 3 || (l.size() == 2 && l.get(0) != l.get(1) - 1))
            .findAny().map(x -> "YES").orElse("NO")));