当前位置：网站首页>Leetcode daily question 540 A single element in an ordered array Valentine's Day special article looking for a single dog in a pile of lovers ~ the clown is myself

Leetcode daily question 540 A single element in an ordered array Valentine's Day special article looking for a single dog in a pile of lovers ~ the clown is myself

2022-07-03 20:56:00 【Ape Xiaofu】

Content of this article ：leetcode A daily topic 540. A single element in an ordered array Valentine's Day Special A bunch of couples looking for a single dog ~ I didn't expect that the clown was myself

Article column ：leetcode A daily topic 《 Punch in daily 》

Recent updates ：2022 year 2 month 13 Japan leetcode A daily topic 1189. “ balloon ” Maximum number of Simple simulation questions ~

Personal profile ： A Junior Program ape in two colleges , In the spirit of paying attention to the foundation , Clock in algorithm , Sharing technology as a personal experience summary blogger , Although you may be lazy sometimes , But I will stick to it , If you like blog posts very much , Suggest looking at the following line ~（ Crazy hints QwQ）

give the thumbs-up Collection Leaving a message. One key, three links _{Care program ape , From you and me}

Write it at the front

Today is Valentine's Day however The profound meaning of this question makes the brain buzzing , Pair up , Find the elements listed , Good guy, break the defense directly , Find a single dog among lovers , I didn't think! , The clown is myself ~

subject

Give you an ordered array of integers only , Each of these elements will appear twice , Only one number will appear once .

Please find and return the number that only appears once .

The solution you design must meet O(log n) Time complexity and O(1) Spatial complexity .

Example

Example 1：

 Input : nums = [1,1,2,3,3,4,4,8,8]
 Output : 2

Example 2:

 Input : nums =  [3,3,7,7,10,11,11]
 Output : 10

Tips

1 <= nums.length <= 10^5
0 <= nums[i] <= 10^5

Ideas

This question examines the knowledge points

There are roughly two ways to solve problems ：

The first one is ： Direct violence AC Because this is an ordered array , If from the first group of elements （ A set of elements is 2 individual ） Start , If a group of elements are different Then there must be a single element between the two . Of course, you can also use hash table counting .
The second kind ： Because the time complexity of this problem is expected to be logn Then we can't use violence , Pairing , Two points search .

Code implementation

violence AC

class Solution {
    
    public int singleNonDuplicate(int[] nums) {
    
        int n= nums.length;
        // Pair up   If there is inconsistency in this group, it is not a couple   Returns the first element 
        for(int i=0;i<n-1;i+=2){
    
            if(nums[i] != nums[i+1]){
    
                return nums[i];
            }
        }
        // If you traverse to the last element, you will directly return this single dog 
        return nums[n-1];
    }
}

Two points （ Valentine's Day Is dichotomy really good ？）

class Solution {
    
    public int singleNonDuplicate(int[] nums) {
    
        int left = 0;
        int right = nums.length-1;
        int mid ;
		// Just set the template directly 
        while(left < right){
    
            mid = left + (right - left )/2;
            if (mid % 2 == 1)mid--;
            if (nums[mid] == nums[mid+1])
                left+=2;
            else {
    
                right = mid;
            }
        }
        return nums[left];
    }
}