A single element in an ordered array -- Valentine's Day mental problems

A single element in an ordered array ——Leetcode Valentine's Day is about mentality

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 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 <= 105
• 0 <= nums[i] <= 105

Attach the title link ：540. A single element in an ordered array - Power button （LeetCode） (leetcode-cn.com)

Personal feelings

yysy, After I understand the topic , I really feel like I've been caught , I admire leetcode The author , Among thousands of questions, cold food was found for him to kill , Valentine's Day is devoted to my mentality , How come everyone else is in pairs, right , Man, I'm unique , Put it here and hit the keyboard, right . Scald ！

Answer key

There's nothing to say , Two point search to judge the odd and even subscript is over

Because there is only one unique and ordered , So we can assume that the subscript of the unique element is x, Its left subscript y, If nums[y] = nums[y+1], be y For the even , alike , For the right , If nums[y] = nums[y+1], be y It's odd .
Based on this , You can set binary search .

I am here leetcode The antithesis of , You can have a look at what you need Two points search - A single element in an ordered array - Power button （LeetCode） (leetcode-cn.com)

code（ Full version ）

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

class Solution 
{
    
public:
    /// <summary>
    ///  Two points search 
    ///  Because there is only one unique and ordered 
    ///  So suppose the only subscript is x, Its left subscript y, If nums[y] = nums[y+1], be y For the even 
    ///  alike , For the right ,  If nums[y] = nums[y+1], be y It's odd 
    ///  Set up a two-point search according to the appeal 
    ///  At the beginning , The boundary on the left is 0, The boundary on the right is n-1,n Is the number of array elements 
    ///  Every time I look up mid Take the middle of the left boundary and the right boundary , Divide parity judgment 
    ///  When mid In an odd number of , Judge nums[mid] == nums[mid-1]
    ///  When mid For even when , Judge nums[mid] == nums[mid+1]
    ///  The above set up a  mid < x,  conversely mid > x
    /// </summary>
    /// <param name="nums"></param>
    /// <returns></returns>
    int singleNonDuplicate(vector<int>& nums) 
    {
    
        int n = nums.size();
        //  A special case , There is only one number 
        if (n == 1)
        {
    
            return nums[0];
        }
        int left = 0, right = n - 1;
        //  Two points search 
        while (left < right)
        {
    
            int mid = left + (right - left) / 2;
            if (mid % 2 == 0 && nums[mid] == nums[mid + 1] ||
                mid % 2 == 1 && nums[mid] == nums[mid - 1])
            {
    
                left = mid + 1;
            }
            else
            {
    
                right = mid;
            }
        }
        return nums[left];
    }
};

int main(int argc, char** argv)
{
    
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i)
    {
    
        cin >> nums[i];
    }
    //  Make sure the data you enter is in order 
    sort(nums.begin(), nums.end());
    Solution sol;
    cout << sol.singleNonDuplicate(nums) << endl;

	return 0;
}

The latter

Today is the day of being killed ...