美文网首页
异或运算的应用,今日头条面试算法题

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

作者: 今年小学一年级 | 来源:发表于2018-08-13 01:19 被阅读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。

    相关文章

      网友评论

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

          本文链接:https://www.haomeiwen.com/subject/anisbftx.html