LeetCode_二分搜索_中等_540.有序数组中的单一元素

偏执的太偏执、 2023-10-06 23:48 3阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

**给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。**

请你找出并返回只出现一次的那个数。

**你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。**

**示例 1：**  
输入: nums = \[1,1,2,3,3,4,4,8,8\]  
输出: 2

**示例 2：**  
输入: nums = \[3,3,7,7,10,11,11\]  
输出: 10

**提示：**  
1 <= nums.length <= 105  
0 <= nums\[i\] <= 105

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/single-element-in-a-sorted-array

## 2.思路 ##

（1）二分搜索  
思路参考[该 LeedCode 用户题解][LeedCode]。

题目要求算法的时间复杂度为 O(logn)，所以首先想到二分搜索，但是关键在于**如何对数组 nums 进行二分**。

① 由题目可知，有序数组中每个元素都会出现两次，唯有一个数只会出现一次，以数组 \[1, 1, 2, 3, 3, 4, 4, 8, 8\] 为例，元素 2 只出现了一次；  
② 如果将元素 2 去掉，那么数组中的所有元素均出现了2 次，并且可以组成 4 个相等数对：\[1, 1\]、\[3, 3\]、\[4, 4\]、\[8, 8\]，但是 2 的出现，破坏了原来的相等数对（并且数组长度也由偶数变成了奇数）：\[1, 1\]、\[2 3\]、\[3, 4\]、\[4, 8\]、\[8, \]；  
③ 此时我们可以发现：**元素 2 之前的相等数对仍然存在，而之后的相等数对被破坏**，所以我们将这一点作为二分的依据！

## 3.代码实现（Java） ##

//思路1————二分搜索
    class Solution {
        
        public int singleNonDuplicate(int[] nums) {
        
            int length = nums.length;
            int left = 0;
            int right = length / 2;
            while (left < right) {
        
                int mid = (left + right) / 2;
                int index = mid * 2;
                if (nums[index] != nums[index + 1]) {
        
                	//当前数对的两个元素不相等，故只出现一次的数在左边
                    right = mid;
                } else {
        
                	//当前数对的两个元素相等，故只出现一次的数在右边
                    left = mid + 1;
                }
            }
            return nums[left * 2];
        } 
    }

[LeedCode]: https://leetcode.cn/problems/single-element-in-a-sorted-array/solution/zhao-dao-er-duan-xing-jiu-shi-jiandan-by-hp3p/