删除元素专题

大家好我是苏麟 , 今天带来第三关黄金挑战关 .

今天有几道小题

数组中只出现一次的元素

题目 :

LCR 070. 有序数组中的单一元素 : 

有序数组中只出现一次的元素

分析  :

因为这里肯定会出现一个单个数字 , 所以不考虑都是双数的存在 .

第一种方法 : 最直接的方法就是遍历比较 , 让nums[i]和nums[i+1]比较 , 如果相同就比较下一组 , 如果 i=nums.length就说明 最后一个元素是单个的 , -1不用管 , 因为不到-1就返回了.

第二种方法 : 二分法 : 

//0 1 2 3 4 5 6 7 8 9 10 元素下标

//1 1 2 2 3 3 4 5 5 6 6  元素值

在没有单个元素之前判断方式nums[i] == nums[i+1] , 在有了单个元素之后之前那只种就比较不了改用 nums[i] -- nums[i - 1] ,所以判断mid % 2 == 0很重要 , 之后就开始收缩 , 逐步完成搜索 .

第三种方法 : 位运算

0 ^ 0 = 0
a ^ a = 0
a ^ b ^ a = b

解析 : 

LeetCode

普通 

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int i = 0;
        for( i = 0; i< nums.length - 1 ;i++){
            if(nums[i] == nums[i + 1]){
                i++;
            }else{
                return nums[i];
            }
        }
        if(i == nums.length - 1){
            return nums[i];
        }
        //由于题目特性 不会走到这里
        return -1;  
    }
}

二分法

//二分法
class Solution {
    public int singleNonDuplicate(int[] nums) {
        //0 1 2 3 4 5 6
        //1 1 2 3 3 4 4
        int left  = 0 ;
        int right = nums.length - 1;
        while(left < right){
            int mid = left + (right - left) / 2 ;
            if(mid % 2 == 0){
                if(nums[mid] == nums[mid + 1]){
                    left = mid + 1;
                }else{
                    right = mid;
                }
            }else{
                if(nums[mid] == nums[mid-1]){
                    left = mid + 1;
                }else{
                    right = mid;
                }
            }
        }
        return nums[left];
    }
}

 位运算

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