【LeetCode每日一题】——540.有序数组中的单一元素

一【题目类别】

• 二分查找

二【题目难度】

• 中等

三【题目编号】

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

四【题目描述】

• 给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
• 请你找出并返回只出现一次的那个数。
• 你设计的解决方案必须满足 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$

七【解题思路】

• 主要还是二分查找的思路
• 只是判断条件有所变化，注意读题目：如果某一部分之前没有单个元素，那么此部分长度肯定为偶数，索引也就是奇数，反之长度就为奇数，索引也就是偶数
• 所以我们还是得到中间元素的索引，如果索引为奇数，那么说明前面都是成对出现的，也就没有单一元素，但是还需要判断后一个和前一个是否相等，也就是判断是否是一堆，如果是的话，说明左面也就没有单一元素，那么修改左索引下标向右
• 如果索引为偶数，说明左面部分肯定有单个元素，修改右索引下标向左
• 最后还需要注意while的判断条件为左索引要小于右索引，不能是小于等于，否则会死循环

八【时间频度】

• 时间复杂度：$O(lo{g}_{2}N)$，其中$N$为数组元素个数
• 空间复杂度：$O(1)$

九【代码实现】

1. Java语言版

package BinarySearch;

public class p540_SingleElementInSortedArray {
    

    public static void main(String[] args) {
    
        int[] nums = {
    1, 1, 2, 3, 3, 4, 4, 8, 8};
        int res = singleNonDuplicate(nums);
        System.out.println("res = " + res);
    }

    public static int singleNonDuplicate(int[] nums) {
    
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
    
            int mid = left + (right - left) / 2;
            if (mid % 2 == 1) {
    
                mid--;
            }
            if (nums[mid] == nums[mid + 1]) {
    
                left = mid + 2;
            } else {
    
                right = mid;
            }
        }
        return nums[left];
    }

}

2. C语言版

#include<stdio.h>

int singleNonDuplicate(int* nums, int numsSize)
{
    
	int left = 0;
	int right = numsSize - 1;
	while (left < right)
	{
    
		int mid = left + (right - left) / 2;
		if (mid % 2 == 1)
		{
    
			mid--;
		}
		if (nums[mid] == nums[mid + 1])
		{
    
			left = mid + 2;
		}
		else
		{
    
			right = mid;
		}
	}
	return nums[left];
}

/*主函数省略*/

十【提交结果】

1. Java语言版
   

2. C语言版