异或运算的应用,今日头条面试算法题

2018-08-13  本文已影响0人  今年小学一年级

原题

  1~n放在含有n+1个元素的数组中,只有唯一的一个元素值重复,其它均只出现
一次。要求时间复杂度O(n),空间复杂度O(1)。

题解(Java)

public class Repeat {

  //利用求和作差求重复数
  public static int getRepeatNumber1(int[] arr) {
    if (arr == null) {
      return -1;
    } else {
      //数组的长度为n+1,求1~n的和
      int sum = 0;
      int n = arr.length - 1;
      if (n % 2 == 0) {
        sum = (n + 1) * (n / 2);
      } else {
        sum = (n + 1) * (n / 2) + (n / 2 + 1);
      }
      int sumArr = 0;
      for (int i = 0; i < arr.length; i++) {
        sumArr += arr[i];
      }
      return sumArr - sum;
    }
  }

  //利用异或求重复数
  public static int getRepeatNumber2(int[] arr) {
    if (arr == null) {
      return -1;
    } else {
      //数组的长度为n+1,求1~n的异或结果
      int orSum = 0;
      int n = arr.length - 1;
      //类似加法运算律,快速求1~n的异或结果
      if (n % 4 == 0) {
        orSum = n;
      } else if (n % 4 == 1) {
        orSum = 1;
      } else if (n % 4 == 2) {
        orSum = n + 1;
      } else {
        orSum = 0;
      }

      int orSumArr = 0;
      for (int i = 0; i < arr.length; i++) {
        orSumArr ^= arr[i];
      }
      return orSumArr ^ orSum;
    }
  }

  public static void main(String[] args) {
    int[] arr = {1, 2, 3, 3, 4};
    int result = getRepeatNumber2(arr);
    System.out.println(result);
  }
}

思考

   此题有两种解法。
  1. 求数组的和,然后求1~n的和,二者作差,结果即为重复数,比较巧妙的想法。看过网上的讨论后,有人说其实这题想考的是异或运算的应用,后来才出现了这种奇妙的解法。不知道出此题的人当初是不是这么想的,还是挺有意思的。在面试的过程中,一开始其实我并没找到空间复杂度O(1)的解法,面试官给出了提示,说可考虑用异或去做。从这方面也可以说明此题的本意可能是为了考察异或运算的应用吧。
  2. 关于异或运算的详细介绍,大家可以从网上查到。其主要的性质就是,两个相同的数异或结果为0,任何数异或0,结果为其本身,同时异或满足交换律和结合率。利用这几个性质就能解决此题。与解法1思路相同,首先求出1~n异或的结果,然后求出数组所有数字的异或结果,二者作异或运算,结果即为重复的数字。
  证明:
  记1~n异或结果为t1,重复的目标数字为k,那么数组的异或结果即为t1^k。二者异或结果为:t1^t1^k=k。

上一篇下一篇

猜你喜欢

热点阅读