【算法题解】 Day20 查找

sidiot

发布于 2023-08-26 19:34:38

2650

发布于 2023-08-26 19:34:38

文章被收录于专栏：技术大杂烩

剑指 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 &amp;&amp; rightIdx < nums.length &amp;&amp; nums[leftIdx] == target &amp;&amp; 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 &amp;&amp; nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}