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

彭晨涛 • 2020年2月25日 01:21 • 算法 • 阅读 67

原题

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

示例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)时间复杂度。

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

前面的元素个数为偶数个，则除去选中本身的这一对，前面的元素个数为奇数个，说明单一元素出现在该元素前面，可以把要查找的结束位置指向当前元素对之前，在图中下一步指向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/

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

原题

解法

思想

代码

相关推荐

发表回复