java - 程序在数组中查找与给定值异或的对

Question

我得到一个数组和一个值 x。

输入示例:

2 3
1 2

其中 n(数组长度)= 2，值 x = 3，下一行 (1, 2) 包含数组中的值。我必须找到索引对 i, j 以便 a[i] XOR a[j] = x。

我实现了什么:

import java.util.HashSet;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
   Scanner sc = new Scanner(System.in);

   int n = sc.nextInt();
   int x = sc.nextInt();

   int[] arr = new int[n];

   HashSet<Integer> hash = new HashSet<Integer>();

   for (int i = 0; i < n; i++) {
     arr[i] = sc.nextInt();
     hash.add(arr[i]);
   }

   int count = 0;

   for (int i = 0; i < n; i++) {
     if (hash.contains(arr[i]^x)) {
       count++;
     }
   }

   System.out.println(count/2);
  }

}

我将结果除以二，因为我们只想计算给定的对一次(只计算 [1, 2] 而不是 [1, 2] 和 [2, 1])。

我通过了上面给定的测试，输出为 1，并通过了这个补充测试，输出为 2。

6 1
5 1 2 3 4 1

但是我似乎没有通过一些我看不到的额外的。

Answer 1

问题是您检查了“包含”，但对于重复值，这只会返回一次。通过使用集合，您可以丢弃重复项。相反，您应该有一个包含出现次数的 HashMap:

Map<Integer, Integer> hash = new HashMap<>();

for (int i = 0; i < n; i++) {
    arr[i] = sc.nextInt();
    if (!hash.containsKey(arr[i])) {
        hash.put(arr[i], 0)
    }
    hash.put(arr[i], hash.get(arr[i]) + 1);
}

int count = 0;

for (int i = 0; i < n; i++) {
    if (hash.containsKey(arr[i]^x)) {
        count += hash.get(arr[i]^x);
    }
}