】 【 LeetCode daily one problem - 540. The order of a single element of the array

一【题目类别】

• 二分查找

二【题目难度】

• 中等

三【题目编号】

• 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$

七【解题思路】

• 主要还是二分查找的思路
• Only the judgment conditions have changed,注意读题目：If a section does not have a single element before it,Then the length of this part must be even,index is odd,Otherwise, the length is an odd number,The index is also an even number
• So we still get the index of the middle element,如果索引为奇数,Then it means that the previous ones appear in pairs,There is no single element,But it is also necessary to judge whether the latter and the former are equal,That is to judge whether it is a pile,如果是的话,Explain that there is no single element on the left,Then modify the left index subscript to the right
• If the index is even,Explain that there must be a single element in the left part,Modify the right index subscript to the left
• 最后还需要注意whileThe judgment condition is that the left index is less than the right index,不能是小于等于,否则会死循环

八【时间频度】

• 时间复杂度：$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语言版