leetcode 12.21-12.27

2020-12-27

191 位1的个数
41 缺失的第一个正整数

191. 位1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

思路：n & (n - 1)

AC代码：

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        return bin(n).count('1')
      
class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        count = 0
        while n :
            count += 1
            n &= (n - 1)
        return count

41. 缺失的第一个正整数

给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。

示例 1:

输入: [1,2,0]
输出: 3

示例 2:

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

示例 3:

输入: [7,8,9,11,12]
输出: 1

提示：

你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/first-missing-positive
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：考虑正整数出现在数组的对应下标处，即符合要求的数组应该是[1, 2, 3, …]这样的排列，可以通过交换[1, N]之间的数字得到这样的排列。遍历一遍数组，交换数字，数组中[1, N]之间的数都到了对应的位置，再遍历一遍数组，如果$nums[i] - 1 != i$，那么返回$i + 1$，否则返回$N+1$。

题解里的哈希表方法很巧妙，学习：

将数组中所有小于等于 0 的数修改为 $N+1$；
遍历数组中的每一个数 $x$，它可能已经被打了标记，因此原本对应的数为$|x|$，如果$|x|\in [1, N]$，那么数组中的第$|x| - 1$个位置的数标记为负数
在遍历完成之后，如果数组中的每一个数都是负数，那么答案是 $N+1$，否则答案是第一个正数的位置加 1。

AC代码：

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        i = 0
        while i < len(nums):
            if 0 < nums[i] <= len(nums) and nums[i] != nums[nums[i] - 1]:
                tmp = nums[i]
                nums[i], nums[tmp - 1] = nums[tmp - 1], nums[i]
            else: i += 1
        
        for i in range(len(nums)):
            if nums[i] - 1 != i:
                return (i + 1)
        return len(nums) + 1