LeetCode每日一题540---有序数组中的单一元素

一、题目描述

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

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

你设计的解决方案必须满足 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 <= 105
0 <= nums[i] <= 105

二、解题思路

这道题目有一定的规律性，我们可以按照规律性进行解题，假设数组的大小为1，那么直接return nums[0]就可以了，如果数组大小不是1，那么我们可以想一下 这个单独出现的数可以在下标为1的地方么，也就是第2个位置的，显然是不可以的， 因为如果这个单独出现的数在下标为1，说明下标为0的数也是单独的，这和题目相悖，那么这个数可以在下标为3的位置么，同样也不行，因为下标为3，说明前面还有3个数，这3个数无法组成两对一样的数，这也与题目相悖，一次类推，单独出现的数也不能在下标为5、7、9...的位置，也就是说这个单独的数的下标一定是偶数，所以我们可以从头到尾，步长为2进行遍历。

三、代码

class Solution(object):
    def singleNonDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        # 特殊情况
        if n==1 :
            return nums[0]
        a = 0
        while a<n+1:
        # 遍历到最后一个元素还没有找到，说明最后一个元素一定是单独出现的数
            if a == n-1:
                return nums[a]
            # 如果下标为偶数的不是单独出现的数，那么他一定与后面的数相同，否则就是单独出现的数
            if(nums[a]!=nums[a+1]):
                return nums[a]
            a = a+2    

        
            
        

原文地址：https://blog.csdn.net/niulinbiao/article/details/143656962

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！