剑指offer -- 查找算法

发表于 | 分类于
字数统计: 2.3k | 阅读时长 ≈ 10
孤独的树

剑指offer – 查找算法

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

Difficulty: 简单

找出数组中重复的数字。

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

示例 1：

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

限制：

2 <= n <= 100000

Solution

方法一：计数方法

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        vector<int> res(nums.size());
        for (int i = 0; i < nums.size(); ++i) {
            if (res[nums[i]] == 1) return nums[i];
            else res[nums[i]]++;
        }
        return -1;
    }
};

时间复杂度：$O(N)$，一次遍历

空间复杂度：$O(N)$， res 数组占用额外空间

方法二：原地交换

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        for (int i = 0; i < nums.size(); ++i) {
			// 只要当前索引位置不是对应的数字，就一直寻找
            while (nums[i] != i) {
                if (nums[i] == nums[nums[i]]) return nums[i];
                swap(nums[i], nums[nums[i]]);
            }
        }
        return -1;
    }
};

时间复杂度：$O(N)$，一次遍历

空间复杂度：$O(1)$， 原地操作，无额外空间消耗。

方法三：替换法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < nums.size(); ++i) {
			int index = nums[i] % n;
            if (nums[index] >= n) {
                return index;
            }
            nums[index] += n;
        }
        return -1;
    }
};

时间复杂度：$O(N)$，一次遍历

空间复杂度：$O(1)$， 原地操作，无额外空间消耗。

注意：方法二，只能返回随机一个重复值（排列中最靠前的那个重复数字），方法一，方法三可以返回第一个（最小）重复值。

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

Difficulty: 中等

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:

现有矩阵 matrix 如下：

1
2
3
4
5
6
7
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

给定 target = 5，返回 true。

给定 target = 20，返回 false。

限制：

0 <= n <= 1000

0 <= m <= 1000

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        int n = matrix.size();
        // 判断是否为空集合
        if (!n) return false;
        int m = matrix[0].size();

        // 先从最右上角开始往左下角找
        int i = 0, j = m - 1;
        while (j >= 0 && i < n) {
            if (target == matrix[i][j]) return true;
            // 大了则向右找
            else if (target < matrix[i][j]) j--;
            // 小了则向左找
            else i++;
        }
        return false;
    }
};

时间复杂度：$O(N + M)$，其中，N 和 M 分别为矩阵行数和列数，此算法最多循环M+N 次。

空间复杂度：$O(1)$，只需要 i， j 两个变量即可。

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

Difficulty: 简单

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

示例 1：

1
2
输入：[3,4,5,1,2]
输出：1

示例 2：

1
2
输入：[2,2,2,0,1]
输出：0

Solution

方法一：排序

1
2
3
4
5
6
7
class Solution {
public:
    int minArray(vector<int>& numbers) {
        sort(numbers.begin(), numbers.end());
        return numbers.front();
    }
};

时间空间复杂度基于排序算法的时间空间复杂度。

方法二：一次遍历

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int minArray(vector<int>& numbers) {
        if (numbers.empty()) return 0;
        // 也即是 数组中第一个降序的数字
        for (int i = 1; i < numbers.size(); i++) {
            if (numbers[i] < numbers[i - 1]) return numbers[i];
        }
        return numbers[0];
    }
};

时间复杂度：$O(N)$，N为数组长度

空间复杂度：$O(1)$，无额外空间消耗

方法三：二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minArray(vector<int>& numbers) {
        int n = numbers.size();
        int i = 0, j = n - 1;
        while (i < j) {
            int m = (i + j) / 2;
            // 如果中点元素大于右值 则说明当前翻转点在右侧 (m , j]
            if (numbers[m] > numbers[j]) i = m + 1;
            // 如果中点元素小于右值 则说明当前翻转点在左侧 [i , m]
            else if (numbers[m] < numbers[j]) j = m;
            // 如果相等，则缩小 右边界 范围即可
            else j--;
        }
        return numbers[i];
    }
};

时间复杂度：$O(\log N)$

**空间复杂度：**只需要 i，j，m 变量即可

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

Difficulty: 简单

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

示例:

1
2
3
4
5
s = "abaccdeff"
返回 "b"

s = "" 
返回 " "

限制：

0 <= s 的长度 <= 50000

Solution

方法一：哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    char firstUniqChar(string s) {
        unordered_map<int, int> mp;
        for (const auto& a : s) {
            mp[a - 'a']++;
        }
        for (const auto& a : s) {
            if(mp[a - 'a'] == 1) return a;
        }
        return ' ';
    }
};

时间复杂度：$O(N)$，N 为数组长度

空间复杂度：$O(1)$，最多 26 个字符

方法二：哈希表优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    char firstUniqChar(string s) {
        vector<char> keys;
        unordered_map<char, bool> dic;
        for(char c : s) {
            // 如果 c 不在 map 里面，将 c push  keys 中
            // key 中包含着非重复的数，最大 26 个
            if(dic.find(c) == dic.end())
                keys.push_back(c);
            // 如果 map 中没有 c，将 map value 置 true
            dic[c] = dic.find(c) == dic.end();
        }
        // 在 keys 中遍历第一次出现 true 即可
        for(char c : keys) {
            if(dic[c]) return c;
        }
        return ' ';
    }
};

时间和空间复杂度均与 “方法一” 相同，而具体分析：方法一 需遍历 s 两轮；方法二 遍历 s 一轮，遍历 keys 一轮（ dic, keys 的长度都不大于 26 ）。空间上，方法二多了 keys，但是其长度最大为 26；

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

Difficulty: 简单

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

示例 1:

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

示例 2:

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

限制：

0 <= 数组长度 <= 50000

Solution

方法一：哈希表

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int search(vector<int>& nums, int target) {
        map<int, int> mp;
        for (const auto& num : nums) {
            mp[num]++;
        }
        return mp.find(target) == mp.end() ? -1 : mp[target];
    }
};

时间复杂度：$O(N)$，N 为数组长度，一次遍历构建哈希表。

空间复杂度：$O(N)$，哈希表所占额外空间。

方法二：二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int len = nums.size();
        int left = 0, right = len - 1;
        int count = 0;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] < target) left = mid + 1;
            // 关键在于如果 >= 情况下都让 right = mid
            // 这样可以找到最左边一个符合条件的位置
            else right = mid;
        }
        while (left < len && nums[left++] == target) count++;
        return count;
    }
}；

时间复杂度：$O(\log N)$，N 为数组长度。

空间复杂度：$O(1)$，left, right, mid, count 几个变量所需的额外空间。

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

Difficulty: 简单

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

示例 1:

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

示例 2:

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

限制：

1 <= 数组长度 <= 10000

Solution

方法一：一次遍历

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] != i) return i;
        }
        return nums.size();
    }
};

时间复杂度：$O(N)$，N 为数组长度

空间复杂度：$O(1)$，无需额外空间

方法二：二分查找

**注意：**看个人喜好选择自己更容易理解的版本，本人更倾向版本二。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();     
        // 版本一：
        // 取小于等于版本，也就是 ( ] right 可以取到，所以 right = n - 1;
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == mid) left = mid + 1;
            else right = mid - 1; // right 可以取到，所以 mid - 1
        }
        return left;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        // 版本二：
        // 取小于版本，也就是 ( ) right 不可以取到，所以 right = n;
        int left = 0, right = n;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] == mid) left = mid + 1;
            else right = mid;  // right 取不到 等同于 mid - 1
        }
        return left;
    }
};

时间复杂度：$O(\log N)$，N 为数组长度。

空间复杂度：$O(1)$，left, right, mid 几个变量所需的额外空间。

参考资料

图解算法数据结构 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com) 官方题解



----------- 本文结束 -----------




0%