LeetCode 剑指Offer

剑指 Offer 03. 数组中重复的数字

题目描述

​ 找出数组中重复的数字。

​ 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

  • 实例：

    1
    2
    3
    输入：
    [2, 3, 1, 0, 2, 5, 3]
    输出：2 或 3

  • 提示

    • 2 <= n <= 100000

解题思路

  • 解题思路:

    1. 使用辅助空间，哈希表；
    2. 交换位置，以数组本身作为哈希表。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 哈希表
class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        dic = {}
        for num in nums:
            if num not in dic:
                dic[num] = 1
            else:
                return num
            
# 交换位置
class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        i = 0
        while i < len(nums):
            if i == nums[i]:
                i += 1
                continue
            if nums[nums[i]] == nums[i]:
                return nums[i]
            nums[nums[i]],nums[i] = nums[i], nums[nums[i]]

剑指 Offer 53 - I. 在排序数组中查找数字 I

题目描述

​ 统计一个数字在排序数组中出现的次数。

  • 实例

    1
    2
    3
    4
    5
    输入: nums = [5,7,7,8,8,10], target = 8
    输出: 2
        
    输入: nums = [5,7,7,8,8,10], target = 6
    输出: 0

  • 提示

    • 0 <= nums.length <= 10^5
    • -10^9 <= nums[i] <= 10^9
    • nums是一个非递减数组
    • -10^9 <= target <= 10^9

解题思路

  1. 哈希表/遍历计数

  2. 双指针中间逼近

  3. 二分法

    其中 二分法为双指针法的优化，从O(n/2)=> O(logn)

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # 解法1
        hash = {}
        for num in nums:
             if num not in hash:
                 hash[num] = 1
             else:
                 hash[num] += 1
         return hash.get(target, 0)

        # 解法2
         sum = 0
         for num in nums:
             if num == target:
                 sum += 1
         return sum

        # 解法3 双指针法
         left, right = 0, len(nums) - 1
         while left <= right:
             if nums[left] > target or nums[right] < target:
                 return 0
             if nums[left] < target:
                 left += 1
             if nums[right] > target:
                 right -= 1
             if nums[left] == target and nums[right] == target:
                 return right - left + 1
         return 0

        # 解法4 二分法
        # 搜索右边界 right
        i, j = 0, len(nums) - 1
        while i <= j:
            m = (i + j) // 2
            if nums[m] <= target:
                i = m + 1
            else:
                j = m - 1
        right = i

        if j >= 0 and nums[j] != target:
            return 0
        # 搜索左边界 left

        i = 0
        while i <= j:
            m = (i + j) // 2
            if nums[m] < target:
                i = m + 1
            else:
                j = m - 1
        left = j
        return right - left - 1

剑指 Offer 53 - II. 0～n-1中缺失的数字

题目描述

​ 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

  • 示例

    1
    2
    3
    4
    5
    输入: [0,1,3]
    输出: 2
        
    输入: [0,1,2,3,4,5,6,7,9]
    输出: 8

  • 限制

    • 1 <= 数组长度 <= 10000

解题思路

1. 数学求和...
 2. 双指针
 3. 二分法: 找中值，如果中值的下标位置，`index == value`。说明中值前的值没问题，到中值后面的找，否则，到中值前找。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        
		# 数学求和 等差数列，首项为0，公差为1，项数为len(nums)+1
		return len(nums)*(len(nums)+1)//2 - sum(nums)
    	
		# 双指针
        left, right = 0, len(nums)-1
        if nums[0] != 0:
            return 0
        if nums[-1] != len(nums):
            return len(nums)
        while left < right:
            if nums[left+1] - nums[left] != 1:
                return nums[left] + 1
            elif nums[right] - nums[right-1] != 1:
                return nums[right-1] + 1
            left,right = left + 1, right -1

		# 二分法
        l, r = 0, len(nums) - 1
        while l <= r:
            m = (l + r) // 2
            if nums[m] == m:
                l = m + 1
            else:
                r = m - 1
        return l