540. 有序数组中的单一元素

淩亂°似流年 2024-04-01 16:07 92阅读 0赞

### 540. 有序数组中的单一元素 ###

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

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

你设计的解决方案必须满足  O ( l o g n ) O(log n) O(logn) 时间复杂度和  O ( 1 ) O(1) 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 < = n u m s . l e n g t h < = 1 0 5 1 <= nums.length <= 10^5 1<=nums.length<=105  
 0 < = n u m s \[ i \] < = 1 0 5 0 <= nums\[i\] <= 10^5 0<=nums\[i\]<=105

#### 思路：（二分查找） ####

*  只出现一次的元素所在下标 x 一定是偶数，可以在偶数下标范围内二分查找;
 *  由于只出现一次的元素所在下标 x 的左边有偶数个元素，且都满足 n u m s \[ l o c \] = = n u m s \[ l o c + 1 \] nums\[loc\] == nums\[loc+1\] nums\[loc\]==nums\[loc\+1\]，所以当满足 n u m s \[ l o c \] = n u m s \[ l o c + 1 \] nums\[loc\]=nums\[loc+1\] nums\[loc\]=nums\[loc\+1\]时，该元素一定在右边，则  l = m + 1 l = m+1 l=m\+1;
 *  满足 n u m s \[ l o c \] ! = n u m s \[ l o c + 1 \] nums\[loc\] != nums\[loc+1\] nums\[loc\]!=nums\[loc\+1\]，则该元素可能就是在本坐标，或者是左边，令$ h = m$ ;
 *  直到$l == h $时，找到本元素的下标

#### 代码：（Java） ####

public class Single_element {
        
    
    	public static void main(String[] args) {
        
    		// TODO 自动生成的方法存根
    		int [] nums = {
        1,1,2,3,3,4,4,8,8};
    		System.out.println(singleNonDuplicate(nums));
    	}
    	 public static int singleNonDuplicate(int[] nums) {
        
    		 int l = 0, h = nums.length/2;
    		 while(l < h) {
        
    			 int m = l + (h - l) / 2;
    			 int loc = m * 2;
    			 if(nums[loc] == nums[loc + 1]) {
        
    				 l = m + 1;
    			 }else {
        
    				 h = m;
    			 }
    		 }
    		 return nums[2 * l];
    	 }
    }

##### 复杂度分析： #####

*  时间复杂度： O ( l o g ⁡ n ) O(log⁡n) O(log⁡n)，其中  n n n 是数组  n u m s nums nums 的长度。需要在偶数下标范围内二分查找，二分查找的时间复杂度是  O ( l o g ⁡ n ) O(log⁡n) O(log⁡n)。
 *  空间复杂度： O ( 1 ) O(1) O(1)。

##### 注：仅供学习参考 #####

来源：[力扣][Link 1]

[Link 1]: https://leetcode.cn/problems/single-element-in-a-sorted-array/description/