2022.02.14_ Daily question leetcode five hundred and forty

Title Description

540. A single element in an ordered array

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 <= 10^5
0 <= nums[i] <= 10^5

Answer key 1

Ideas

Use dichotomy , Ensure that the array is in left To right The length of is odd , Through the middle mid Divide the boundary , Judge the length of the left and right sub arrays respectively , Judge the corresponding according to the length mid Nearby values , Find out the result should be in mid Left or right .

Code

class Solution {
    
    public int singleNonDuplicate(int[] nums) {
    
        if (nums.length == 1){
    
            return nums[0];
        }

        int left = 0;
        int right = nums.length - 1;

        while (left < right){
    

            int mid = left + ((right - left) >> 1);

            if ((mid - left + 1) % 2 == 0){
    
                if (nums[mid] != nums[mid - 1]){
    
                    right = mid - 1;
                }else {
    
                    left = mid + 1;
                }
            }else {
    
                if (nums[mid] != nums[mid - 1]){
    
                    left = mid;
                }else {
    
                    right = mid;
                }
            }
        }
        return nums[left];
    }
}

Running results

Answer key 2

Ideas

Because the array is ordered , Therefore, it can be judged by every two numbers , According to whether the XOR result is 0 To determine the result

principle ：
N ^ N == 0
N ^ 0 == N
(A ^ B) ^ C == A ^ (B ^ C)
A ^ B == B ^ A

Code

class Solution {
    
    public int singleNonDuplicate(int[] nums) {
    
        int res = 0;
        for (int i : nums) {
    
            res = i ^ res;
        }
        return res;
    }
}

Running results

expand

package com.nuo.Demo;

import java.util.Arrays;
import java.util.Stack;

/** * @author nuo * @version 1.0 * @description: TODO  XOR search  * @date 2022/1/5 16:49 */
public class s_02{
    

//  An array of integers , Only one number appears an odd number of times , Other numbers appear an even number of times , Find this number 
    public static int select_1(int[] arr) {
    
        int eor = 0;
        for (int i : arr) {
    
            eor = eor ^ i;
        }
        return eor;
    }

//  An array of integers , There are only two numbers  (a , b)  An odd number of times , Other numbers appear an even number of times , Find this number 
    public static int[] select_2(int[] arr) {
    
        int eor = 0;
        for (int i : arr) {
    
            eor = eor ^ i;
        }  // => eor = a ^ b != 0 => eor  One must be  '1'

        //  Original code  &  Complement code 
        int rightOne = eor & (~eor + 1);  // =>  Extract the rightmost  1 , The number of these two is different 
        // eg. eor = 1001 => ~eor = 0110 => ~eor + 1 = 0111 => eor & (~eor + 1) = 0001

        int eor_ = 0;
        for (int j : arr) {
    
            if ((rightOne & j) == 0) {
    
                eor_ = eor_ ^ j;
            }
        }
        return new int[]{
    eor_ , eor_ ^ eor};
    }
}