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

题目

剑指 Offer 03. 数组中重复的数字 难度：easy

找出数组中重复的数字。

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

示例 1：

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

限制：

2 <= n <= 100000
 

方法一：遍历数组

思路

由于只需要找出数组中任意一个重复的数字，因此遍历数组，遇到重复的数字即返回。为了判断一个数字是否重复遇到，使用集合存储已经遇到的数字，如果遇到的一个数字已经在集合中，则当前的数字是重复数字。

• 初始化集合为空集合，重复的数字 repeat = -1

• 遍历数组中的每个元素：

  • 将该元素加入集合中，判断是否添加成功

    • 如果添加失败，说明该元素已经在集合中，因此该元素是重复元素，将该元素的值赋给 repeat，并结束遍历

解题

Python：

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        temp_set = set()
        repeat = -1
        for i in range(len(nums)):
            temp_set.add(nums[i])
            if len(temp_set) < i + 1:
                repeat = nums[i]
                break
        return repeat

Java：

class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        int repeat = -1;
        for (int num : nums) {
            if (!set.add(num)) {
                repeat = num;
                break;
            }
        }
        return repeat;
    }
}

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

题目

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

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

示例 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 <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums 是一个非递减数组
• -10^9 <= target <= 10^9

方法一：二分查找

思路

直观的思路肯定是从前往后遍历一遍。用两个变量记录第一次和最后一次遇见 $\textit{target}$ 的下标，但这个方法的时间复杂度为 $O(n)$，没有利用到数组升序排列的条件。

由于数组已经排序，因此整个数组是单调递增的，我们可以利用二分法来加速查找的过程。

考虑 $\textit{target}$ 在数组中出现的次数，其实我们要找的就是数组中「第一个等于 $\textit{target}$ 的位置」（记为 $\textit{leftIdx}$）和「第一个大于 $\textit{target}$ 的位置减一」（记为 $\textit{rightIdx}$）。当 $\textit{target}$ 在数组中存在时，$\textit{target}$ 在数组中出现的次数为 $\textit{rightIdx}-\textit{leftIdx}+1$。

二分查找中，寻找 $\textit{leftIdx}$ 即为在数组中寻找第一个大于等于 $\textit{target}$ 的下标，寻找 $\textit{rightIdx}$ 即为在数组中寻找第一个大于 $\textit{target}$ 的下标，然后将下标减一。两者的判断条件不同，为了代码的复用，我们定义 binarySearch(nums, target, lower) 表示在 $\textit{nums}$ 数组中二分查找 $\textit{target}$ 的位置，如果 $\textit{lower}$ 为 $\rm true$，则查找第一个大于等于 $\textit{target}$ 的下标，否则查找第一个大于 $\textit{target}$ 的下标。

最后，因为 $\textit{target}$ 可能不存在数组中，因此我们需要重新校验我们得到的两个下标 $\textit{leftIdx}$ 和 $\textit{rightIdx}$，看是否符合条件，如果符合条件就返回 $\textit{rightIdx}-\textit{leftIdx}+1$，不符合就返回 0。
 

解题

Python：

class Solution:
    def search(self, nums: [int], target: int) -> int:
        def helper(tar):
            i, j = 0, len(nums) - 1
            while i <= j:
                m = (i + j) // 2
                if nums[m] <= tar: i = m + 1
                else: j = m - 1
            return i
        return helper(target) - helper(target - 1)

Java：

class Solution {
    public int search(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return rightIdx - leftIdx + 1;
        } 
        return 0;
    }

    public int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

后记

📝 上篇精讲： 【算法题解】 Day19 字符串
💖 我是  𝓼𝓲𝓭𝓲𝓸𝓽，期待你的关注；
👍 创作不易，请多多支持；
🔥 系列专栏： 算法题解