力扣 第540题 有序数组中的单一元素

解题思路：

        因为解决方案必须满足 `O(log n)` 的时间复杂度，和 `O(1)` 的空间复杂度。所以我们首先考虑用二分查找的思想。这个问题的关键是找到我们要找的元素在左边还是右边的判断条件。

        要找的元素在左边还是右边的判断条件是什么呢？题目告诉我们每个元素都会出现两次，唯有一个数只会出现一次。以数组nums = [1,1,2,3,3,4,4,8,8]为例，第一次二分查找时，记录中间元素下标的变量为mid为4，此时num[4]是第二个3，我们将mid减1，得到第一个3，再进行判断：此时mid前面的元素为1,1,2有奇数个，说明在mid左边有一个元素不是重复出现两次，则要找到元素在mid的左边。

把上面的思维转化成代码：

第一步：二分查找 先折半 计算出记录中间元素下标的变量mid

第二步：令mid为此时两个重复元素中的第一个。判断num[mid]是否是重复元素中的第一个，即判断nums[mid] 是否等于nums[mid - 1]，如果等于，说明第一个重复元素不是nums[mid]，而是nums[mid - 1]，所以令mid - = 1。

第三步：判断nums[mid]之前的元素个数是偶数还是奇数。数组中元素下标为当前元素的个数加1，所以mid的前一个元素下标为mid-1，则mid之前有mid-1+1个也就是mid个元素，如果 mid %2 等于 1 说明mid之前有奇数个元素，否则，反之。

第四步：如果mid之前有奇数个元素，说明要找的元素在mid左边，我们令 right = mid - 1。如果mid之前有偶数个元素，说明要找的元素在mid右边，我们令 left = mid + 2。加2是因为mid在重复元素第一个，所以加2而不是加1，是为了避免让mid记录为此时两个重复元素中的第二个，影响后续判断。

注意：有几种特殊情况应提前判断。

• nums的长度为1.直接返回nums[0]。判断条件为：nums.length = 1
• 重复元素在第一个。判断条件为：mid == 0 && nums[mid] != nums[mid + 1]
• 重复元素在最后一个。判断条件为：mid == nums.length-1 && nums[mid] != nums[mid - 1]

  public static int singleNonDuplicate(int[] nums) {
          // 先判断特殊情况
          // 特殊情况1：nums的长度为1.直接返回
          if(nums.length <= 1) {
              return nums[0];
          }
          int left = 0, right = nums.length - 1;
          for( ;left <= right;) {
              int mid = (right + left) / 2;
              // 特殊情况2：重复元素在第一个
              if(mid == 0 && nums[mid] != nums[mid + 1]){
                  return nums[mid];
              }
              // 特殊情况3：重复元素在最后一个
              if(mid == nums.length-1 && nums[mid] != nums[mid - 1]){
                  return nums[mid];
              }
              if(nums[mid] != nums[mid + 1] && nums[mid] != nums[mid - 1]) {
                  return nums[mid];
              }else if(nums[mid] == nums[mid - 1]) {
                  mid = mid -1;
              }
              // 判断前面元素是否是偶数，是,则在右边
              if(mid %2 ==1){  // mid为奇数，则前面元素位奇数个，在左边
                  right = mid - 1;
              }else {
                  left = mid + 2;  // mid在重复元素第一个，所以加2
              }
          }
          return 0;
      }