LeetCode 136.只出现一次的数字-74.搜索二维矩阵-88.合并两个有序数组






常识① : 算法的时空复杂度

常识② : 哈希算法





题目136:只出现一次的数字

happysneaker.com

思路1:

方法有很多,但既然题目说是只存在重复两次和一次的数,那么最简单:考虑用 2倍的 set(nums) - nums本身,这样就得到那个Single one 了。


解1:O(n)

class Solution:
    def singleNumber(self, nums):
        return 2*sum(set(nums))-sum(nums)


思路2:

① 大部分元素重复两次,那么考虑用异或运算符,来挑出Singleone

② 异或^ :  二进制比较,相同为0,不同为1 ,0^x=x

③ 连续对同一个数异或两次那么数值不变,比如 A^B=C  , 那么 C^B=A , 这个道理需要明白,不管中间疑惑了多少个别的值,只要对同一个数异或了 2n 次,那么这个数就是没用的了,因此如果一个List中只有一个数出现了奇数次,那么将整个list遍历异或,最终异或的结果就是这个出现了奇数次的数。


解2:O(n)

class Solution:
    def singleNumber(self, nums):
        a = 0
        for num in nums:
            a  ^= num
        return a

测试用例:[2,1,4,4,2]






题目74:搜索二维矩阵

happysneaker.com

思路:

① 从左到右从上到下均为递增,因此考虑从左上到右下或者从右上到左下的判断顺序,这里采用更高效的从右上到左下的判断顺序:从第一行最后一列的数字point开始与target相比,如果point==target,OK直接返回TRUE说明存在target,如果point>target ,OK向本行向左移一列再次与target比较,如果point<target,说明本行最大的数字都已经小于target,可能的数值只能存在于下面的行了,所以向下移动一行进行比较。

② 考虑从右上到左下的比较顺序的原因:如果从左上到右下比较,那么就得顺序遍历整个矩阵。但是从右上到左下的顺序能够减少比较的次数,从本行最大值开始比较,可以减少判断次数。



解:O(m+n)

class Solution:
    def searchMatrix(self, matrix, target):
        m = len(matrix)
        if m == 0:
            return False
        else:
            n = len(matrix[0])
        
        start = 0
        end = -1
        while start < m and end >= -n :
            point = matrix[start][end]
            if point == target:
                return True
            elif point > target:
                end -= 1
            else:
                start += 1   
        return False






题目88:合并两个有序数组

happysneaker.com


思路:O(n)

去掉两个List中的0然后将nums2追加到nums1中,对nums1排序即可,代码就不写了。





Web安全技术分享
请先登录后发表评论
  • 最新评论
  • 总共0条评论