leetcode540-有序数组中的单一元素

原题

给定一个只包含整数的有序数组,每个元素都会出现两次,唯有一个数只会出现一次,找出这个数。

示例1:

输入: [1,1,2,3,3,4,4,8,8] 输出: 2

示例2:

输入: [3,3,7,7,10,11,11] 输出: 10

注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。

解法

思想

最优解法:二分查找达到O(log n)时间复杂度。

leetcode540-有序数组中的单一元素

保持数组个数为奇数(即永远只包含一个单一元素),每次取中间的元素,如果前面的元素与当前元素相等,又分两种情况:

  • 前面的元素个数为偶数个,则除去选中本身的这一对,前面的元素个数为奇数个,说明单一元素出现在该元素前面,可以把要查找的结束位置指向当前元素对之前,在图中下一步指向2。
  • 前面的元素个数为奇数个,则除去选中本身的这一对,前面的元素个数为偶数个,说明单一元素出现在该元素后面,可以把要查找的开始位置指向当前元素对之后,在图中下一步指向10。

如果当前元素和后面的元素相等情况也是类似的,可以逐一分析。

其他解法:暴力法,异或。

代码

二分查找:

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int start = 0;
        int end = nums.length-1;
        while(start<end){
            int mid = (start+end)/2;
            if(mid%2==0) {
                if(nums[mid-1]==nums[mid]) end = mid-2;
                else if(nums[mid+1] == nums[mid]) start = mid+2;
                else return nums[mid];
            }else{
                if(nums[mid-1]==nums[mid]) start = mid+1;
                else if(nums[mid+1] == nums[mid]) end = mid-1;
                else return nums[mid];
            }
        }
        return nums[start];
    }
}

暴力法:

class Solution {
    public int singleNonDuplicate(int[] nums) {
        for (int i = 0; i < nums.length - 1; i+=2) {
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }
        return nums[nums.length - 1];
    }
}

异或:

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

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode540-%e6%9c%89%e5%ba%8f%e6%95%b0%e7%bb%84%e4%b8%ad%e7%9a%84%e5%8d%95%e4%b8%80%e5%85%83%e7%b4%a0/

发表回复

登录后才能评论