2022.02.14

有序数组中的单一元素

给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。

请你找出并返回只出现一次的那个数。

你设计的解决方案必须满足 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

利用二分法，每经过一次循环都确保数组在left到right上的长度为奇数，通过对中间的mid为界划分，分别判断左右两边子数组的长度，根据长度去判断对应mid 附近的值 ，找出结果应该在mid左边还是右边。

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];
    }
}

因为数组有序，故可以按每两个数进行判断 ，根据异或结果是否为 0 去确定结果

原理 ：
N ^ N == 0
N ^ 0 == N
(A ^ B) ^ C == A ^ (B ^ C)
A ^ B == B ^ A

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

package com.nuo.Demo;

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


public class s_02{

//    一个整数数组，只有一个数字出现了奇数次，其他数字都出现了偶数次，找出这个数
    public static int select_1(int[] arr) {
        int eor = 0;
        for (int i : arr) {
            eor = eor ^ i;
        }
        return eor;
    }

//    一个整数数组，只有两个数字 (a , b) 出现了奇数次，其他数字都出现了偶数次，找出这个数
    public static int[] select_2(int[] arr) {
        int eor = 0;
        for (int i : arr) {
            eor = eor ^ i;
        }  // => eor = a ^ b != 0 => eor 必有一位是 '1'

        //             原码 & 补码
        int rightOne = eor & (~eor + 1);  // => 提取出最右侧的 1 ,这一位俩个数不一样
        // 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};
    }
}