[数据结构与算法]【Leetcode】540. 有序数组中的单一元素

目录

题目

题解

法一：利用字典计数

法二：步长为2的for循环遍历

法三：二分查找

题目

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/single-element-in-a-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出

处。

题解

法一：利用字典计数

上周实验课刚用过这个方法，所以看到这道题的第一个想法就是利用字典计数

用两个for循环，第一遍计数，第二遍找出字典中值为1的对应键

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        dic={}
        for i in nums:
            dic[i]=dic.get(i,0)+1
        for i in dic:
            if dic[i]==1:
                return i

法二：步长为2的for循环遍历

该题除需找数外都会出现两次，利用步长为2的for循环查找，从第1个数开始遍历，当前数应与前一个数相同， 如不相同，前一个数为要找的数

注意：当列表长度为奇时，需额外考虑列表最后一个数为需找数的情况，即函数最后加上return nums[-1]

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        l=len(nums)
        for i in range(1,l,2):
            if nums[i]!=nums[i-1]:
                return nums[i-1]
        return nums[-1]

法三：二分查找

这种方法比起前两个要难想到一点，想要写正确也难点?

最好在纸上列一个列表进行推导，使得i和j的变化不易混乱

利用二分，使m=(i+j)//2，确定单个的数出现在m的前面还是后面

若m为偶，nums[m]应该等于nums[m+1]，如不相等，则m前面的列表出现了单个的数，使j=m；若m为奇，nums[m]应该等于nums[m-1]，如不相等，则m前面的列表出现了单个的数，使j=m

注意：j在变化时，使j=m是为了避免漏下m所在的数即为所找数的情况

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        i=0
        j=len(nums)-1
        m=(i+j)//2
        while i!=j:
            if m%2==0:
                if nums[m]==nums[m+1]:
                    i=m+1
                else:
                    j=m
            else:
                if nums[m]==nums[m-1]:
                    i=m+1
                else:
                    j=m
            m=(i+j)//2
        return nums[i]