蓝桥杯练习020

唯一成对的数

存在一个长度为 N 的数组，其内容为 1 ~ N - 1 连续自然数( N-1 个) 和 1 到 N - 1 中的某个数，即所谓数组中存在唯一成对的数。

此外，数据可能是乱序的。

目标是找出成对的数是什么。

举个栗子

举例来说，[2,3,1,2,4] 就是符合题目描述的数组，其中 2 是问题的解。

知识点

• 知识点 1：数组遍历
• 知识点 2：异或运算

实现思路

不用位运算

我们可以用标记法：

• 先开辟一个辅助数组 h，长度为 N；
• 遍历原数组 a，对 h[a[i]] 自增，即记录 a[i] 出现的次数；
• 遍历数组 h ，如果 h[x]==2 , x 就是答案。

  private static int solve0(int n, int[] arr) {
    
    int[] helper = new int[n];
    for (int i = 0; i < n; i++) {
    
      helper[arr[i]]++;
    }
    for (int i = 0; i < n; i++) {
    
      if (helper[i] == 2) {
    
        return i;
      }
    }
    return -1;
  }

用位运算

我们可以换个角度来求解，即消除 1 ~ N - 1 ，那剩下的就是答案。此时能否直接对原数组用连续异或的方式呢？不行！直接用，会把成对的数消掉。

我们可以把 1 ~ N - 1 和原数组组合起来形成一个新数组，新数组中 1 ~ N - 1 每个数都出现 2 次，目标答案则会出现 3 次。只需对新数组遍历，连续做异或运算，最终结果就是答案。

当然，所谓新数组是为了便于读者理解，实际代码中无需开辟新数组。

  private static int solve(int n, int[] arr) {
    
    int x1 = 0;
    for (int i = 1; i <= n - 1; i++) {
    
      x1 = (x1 ^ i);
    }
    for (int i = 0; i < n; i++) {
    
      x1 = x1 ^ arr[i];
    }
    return x1;
  }

测试

假设把上述两种思路写在方法 solve0 和 solve1 中，可以用下面的 main 方法来输出两种思路的计算结果，看是否一致：

  public static void main(String[] args) {
    
    int N = 1001;
    int[] arr = new int[N];
    for (int i = 0; i < arr.length - 1; i++) {
    
      arr[i] = i + 1;
    }
    //最后一个数，是随机数
    arr[arr.length - 1] = new Random().nextInt(N - 1) + 1;

    //随机下标
    int index = new Random().nextInt(N);
    swap(arr, index, arr.length - 1);

    System.out.println(solve0(N, arr));
    System.out.println("==========");
    System.out.println(solve(N, arr));
  }
  
  /** * 在数组内原址交换元素 * * @param arr * @param i * @param j */
  public static void swap(int[] arr, int i, int j) {
    
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  }

总结

相同的两个数异或后结果为 0 ，任何数和 0 异或后保持不变，这样的特性往往有妙用。

完整代码

import java.util.Random;

public class _01唯一成对的数 {
    
  public static void main(String[] args) {
    
    int N = 1001;
    int[] arr = new int[N];
    for (int i = 0; i < arr.length - 1; i++) {
    
      arr[i] = i + 1;
    }
    //最后一个数，是随机数
    arr[arr.length - 1] = new Random().nextInt(N - 1) + 1;

    //随机下标
    int index = new Random().nextInt(N);
    swap(arr, index, arr.length - 1);

    System.out.println(solve0(N, arr));
    System.out.println("==========");
    System.out.println(solve(N, arr));
  }

  private static int solve0(int n, int[] arr) {
    
    int[] helper = new int[n];
    for (int i = 0; i < n; i++) {
    
      helper[arr[i]]++;
    }
    for (int i = 0; i < n; i++) {
    
      if (helper[i] == 2) {
    
        return i;
      }
    }
    return -1;
  }

  private static int solve(int n, int[] arr) {
    
    int x1 = 0;
    for (int i = 1; i <= n - 1; i++) {
    
      x1 = (x1 ^ i);
    }
    for (int i = 0; i < n; i++) {
    
      x1 = x1 ^ arr[i];
    }
    return x1;
  }

  /** * 在数组内原址交换元素 * * @param arr * @param i * @param j */
  public static void swap(int[] arr, int i, int j) {
    
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  }
}