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

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

您的程序没有正确处理重复的数字。它可以处理 5 1 2 3 4 1，因为 1 不是解决方案的一部分。如果是呢？

假设数字 a[i] ^ a[j] 和 a[i] ^ a[k] 一样是一个解。换句话说，a[j] == a[k]。 hash.contains(arr[i]^x) 行只会计算 a[i] 一次。

您可以通过嵌套 for 循环来解决这个问题。

for (int i = ...) {
  for (int j = ...) {
    if (a[i] ^ a[j] == x) {
      count++;
    }
  }
}

这种方法可以让您摆脱 hash 集。如果您足够聪明地填写 ... 部分，您可以避免重复计算对，并且不必将 count 除以 2.

Answer 2

您将 count 除以 2 作为最终答案的逻辑是不正确的。用以下内容替换您的逻辑：

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

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

   int count = 0;

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

   System.out.println(count);

Answer 3

问题是您检查了 "contains"，但对于重复值，这仅 returns 出现一次。通过使用集合，您可以丢弃重复项。相反，您应该有一个出现次数的 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);
    }
}

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

Program to find pairs in array that XOR to a given value

java

arrays

algorithm

xor