LeetCode刷题计划-Day 4:查找算法(简单)

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

  • 题目描述:

    找出数组中重复的数字。

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

    示例1:

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

    限制:

    • 2 <= n <= 100000
  • 解题思路:

    遍历数组,用哈希表存储出现过的数字:

    func findRepeatNumber(nums []int) int {
        var res int
        existed := make(map[int]struct{}, len(nums)) // Go语言空结构体不占空间;容量是确定的,可以在初始化时分配内存,节约时间
        for _, i := range nums {
            if _, ok := existed[i]; ok {
                res = i
                break
            } else {
                existed[i] = struct{}{}
            }
        }
        return res
    }

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

  • 题目描述:

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

    示例1:

    输入: nums = [5,7,7,8,8,10], target = 8
    输出: 2

    示例2:

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

    提示:

    • 0 <= nums.length <= 105
    • -109 <= nums[i] <= 109
    • nums 是一个非递减数组
    • -109 <= target <= 109
  • 解题思路:

    同上题,使用哈希表保存数字出现次数:

    func search(nums []int, target int) int {
        existed := make(map[int]int, len(nums))
        for _, i := range nums {
            existed[i]++
        }
        if res, ok := existed[target]; ok {
            return res
        }
        return 0
    }

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

  • 题目描述:

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

    示例1:

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

    示例2:

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

    限制:

    • 1 <= 数组长度 <= 10000
  • 解题思路:

    输入是有序的,可以采用二分法查找第一个值不等于索引的元素:

    func missingNumber(nums []int) int {
        return binarySearchMissing(nums, 0, len(nums)-1)
    }
    
    func binarySearchMissing(nums []int, left, right int) int {
        if left > right {
            return left
        }
        mid := left + (right-left)/2
        if nums[mid] == mid {
            return binarySearchMissing(nums, mid+1, right)
        } else {
            return binarySearchMissing(nums, left, mid-1)
        }
    }

你可能感兴趣的