## 题目描述 给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。 请你找出并返回只出现一次的那个数。 你设计的解决方案必须满足 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 <= 10^5 - 0 <= nums[i] <= 10^5 ### 解答 #### 题目思路 题目要求logn的复杂度，不能采用异或求和的方式，因此需要对其采用 #### 代码实现 ```java public int singleNonDuplicate(int[] nums) { int left = 0; int right = nums.length - 1; while(left < right){ int mid = left + (right - left) / 2; // 如果发现了单个的数字 if(mid==0 && nums[1] != nums[0] || mid==nums.length-1 && nums[nums.length-1] != nums[nums.length -2] || nums[mid-1]!=nums[mid] && nums[mid+1] != nums[mid]) return nums[mid]; // 如果选定左侧数字 else if(mid < nums.length -1 && nums[mid]==nums[mid+1]){ // 在单个数字左侧 if(mid%2==0){ left = mid+2; }else{ right = mid-1; } } // 如果选定右侧数字 else if(mid > 0 && nums[mid-1]==nums[mid]){ // 在单个数字右侧 if(mid%2==0){ right = mid-2; }else{ left = mid+1; } } } return nums[left]; } ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复