剑指offer一刷：查找算法

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

难度：简单

方法一：哈希表 / Set

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

作者：Krahets
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/59jyzd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：O(N)，空间复杂度：O(N)。

方法二：原地交换

遍历数组并通过交换操作，使元素的 索引 与 值 一一对应（即 nums[i] = i）

遍历中，第一次遇到数字 x 时，将其交换至索引 x 处；而当第二次遇到数字 x 时，一定有 nums[x] = x，此时即可得到一组重复数字。

class Solution {
    public int findRepeatNumber(int[] nums) {
        int i = 0;
        while(i < nums.length) {
            if(nums[i] == i) {
                i++;
                continue;
            }
            if(nums[nums[i]] == nums[i]) return nums[i];
            int tmp = nums[i];
            nums[i] = nums[tmp];
            nums[tmp] = tmp;
        }
        return -1;
    }
}

作者：Krahets
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/59jyzd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：O(N)，空间复杂度：O(1)。

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

难度：简单

方法一：二分查找

使用二分法分别找到 左边界 left 和 右边界 right ，易得数字 target 的数量为 right - left - 1。

class Solution {
    public int search(int[] nums, int target) {
        // 搜索右边界 right
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] <= target) i = m + 1;
            else j = m - 1;
        }
        int right = i;
        // 若数组中无 target ，则提前返回
        if(j >= 0 && nums[j] != target) return 0;
        // 搜索左边界 right
        i = 0; j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] < target) i = m + 1;
            else j = m - 1;
        }
        int left = j;
        return right - left - 1;
    }
}

作者：jyd
链接：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/solution/mian-shi-ti-53-i-zai-pai-xu-shu-zu-zhong-cha-zha-5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：O(logN)，空间复杂度：O(1)。

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

难度：简单

方法一：二分查找

排序数组中的搜索问题，首先想到 二分法 解决。根据题意，数组可以按照以下规则划分为两部分。

  • 左子数组： nums[i] = i；
  • 右子数组： nums[i] ≠  ；

缺失的数字等于 “右子数组的首位元素” 对应的索引；因此考虑使用二分法查找 “右子数组的首位元素” 。

class Solution {
    public int missingNumber(int[] nums) {
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] == m) i = m + 1;
            else j = m - 1;
        }
        return i;
    }
}

作者：Krahets
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/58ut96/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：O(logN)，空间复杂度：O(1)。

剑指 Offer 04. 二维数组中的查找

难度：中等

方法一：暴力

不多说。。

时间复杂度：O(N×M)，空间复杂度：O(1)。

方法二：线性查找

如下图所示，我们将矩阵逆时针旋转 45°，并将其转化为图形式，发现其类似于二叉搜索树，即对于每个元素，其左分支元素更小、右分支元素更大。因此，通过从“根节点”开始搜索，遇到比 target 大的元素就向左，反之向右，即可找到目标值 target。

“根节点”对应的是矩阵的“左下角”和“右上角”元素，本文称之为标志数，以 matrix 中的左下角元素为标志数 flag，则有:

  1. 若 flag > target，则 target 一定在 flag 所在行的上方，即 flag 所在行可被消去。
  2. 若 flag < target，则 target 一定在 flag 所在列的右方，即 flag 所在列可被消去。

当然，若行索引或列索引越界，则代表矩阵中无目标值。

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int i = matrix.length - 1, j = 0;
        while(i >= 0 && j < matrix[0].length)
        {
            if(matrix[i][j] > target) i--;
            else if(matrix[i][j] < target) j++;
            else return true;
        }
        return false;
    }
}

作者：Krahets
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5vl81e/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：O(N+M)，空间复杂度：O(1)。

剑指 Offer 11. 旋转数组的最小数字

难度：简单

方法一：二分查找

算法流程：

  1. 初始化： 声明 i, j 双指针分别指向 nums 数组左右两端；
  2. 循环二分： 设 m = (i + j) / 2 为每次二分的中点（ "/" 代表向下取整除法，因此恒有 i ≤ m < j），可分为以下三种情况：
    1. 当 nums[m] > nums[j] 时： m 一定在左排序数组中，即旋转点 x 一定在 [m + 1, j] 闭区间内，因此执行 i = m + 1；
    2. 当 nums[m] < nums[j] 时： m 一定在右排序数组中，即旋转点 x 一定在[i, m] 闭区间内，因此执行 j = m；
    3. 当 nums[m] = nums[j] 时： 无法判断 m 在哪个排序数组中，即无法判断旋转点 x 在 [i, m] 还是 [m + 1, j] 区间中。解决方案： 执行 j = j - 1 缩小判断范围。
  3. 返回值： 当 i = j 时跳出二分循环，并返回旋转点的值 nums[i] 即可。
class Solution {
    public int minArray(int[] numbers) {
        int i = 0, j = numbers.length - 1;
        while (i < j) {
            int m = (i + j) / 2;
            if (numbers[m] > numbers[j]) i = m + 1;
            else if (numbers[m] < numbers[j]) j = m;
            else j--;
        }
        return numbers[i];
    }
}

作者：Krahets
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5055b1/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：O(logN)（特殊情况下如 [1, 1, 1, 1] 会退化到 O(N) ），空间复杂度：O(1)。

剑指 Offer 50. 第一个只出现一次的字符

难度：简单

方法一：哈希表

  1. 遍历字符串 s，使用哈希表统计“各字符数量是否 > 1”。
  2. 再遍历字符串 s，在哈希表中找到首个“数量为 1 的字符”，并返回。

class Solution {
    public char firstUniqChar(String s) {
        HashMap dic = new HashMap<>();
        char[] sc = s.toCharArray();
        for(char c : sc)
            dic.put(c, !dic.containsKey(c));
        for(char c : sc)
            if(dic.get(c)) return c;
        return ' ';
    }
}

作者：Krahets
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5vu0zv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：O(N)，空间复杂度：O(1)（只包含小写字母）。

方法二：有序哈希表

在哈希表的基础上，有序哈希表中的键值对是按照插入顺序排序的。基于此，可通过遍历有序哈希表，实现搜索首个“数量为 1 的字符”。

class Solution {
    public char firstUniqChar(String s) {
        Map dic = new LinkedHashMap<>();
        char[] sc = s.toCharArray();
        for(char c : sc)
            dic.put(c, !dic.containsKey(c));
        for(Map.Entry d : dic.entrySet()){
           if(d.getValue()) return d.getKey();
        }
        return ' ';
    }
}

作者：Krahets
链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5vu0zv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间和空间复杂度均与“方法一”相同，而具体分析：方法一需遍历 s 两轮；方法二遍历 s 一轮，遍历 dic 一轮（dic 的长度不大于 26）。

剑指offer刷题

相关

标签