算法分析课程博客分享 3
169. 求众数(Majority Element)
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
解题思路:
这道题属于简单题，因此，我打算在这里提供多种做法。
解法 1: 哈希法
使用 std::unordered_map 容器，将数组里的元素与出现的次数关联在一起，然后返回出现次数大于 len/2 的值。时间复杂度为 O(n)。
int majorityElement(vector<int>& nums) {
std::unordered_map<int, int> count;
int len = nums.size();
for (int i = 0; i < len; ++i)
++count[nums[i]];
len /= 2.0f;
for (auto it = count.begin(); it != count.end(); it++)
if (it->second > len)
return it->first;
}
解法 2: 位运算法
使用一个桶来记录 32 个 bits 在数组中出现的次数。对于返回值，将在桶中出现次数大于 len/2 的 bit 置为 1。时间复杂度为 O(n)，但是会慢于哈希法。
int majorityElement(vector<int>& nums) {
int count[32] = { 0 };
int len = nums.size();
for (int i = 0; i < len; ++i) {
for (int j = 0; j < 32; ++j) {
count[j] += ((nums[i] >> j) & 1);
}
}
int ans = 0;
for (int i = 0; i < 32; ++i) {
if (count[i] > len/2) {
ans |= (1 << i);
}
}
return ans;
}
解法 3: 数组法
由于题目限定了众数在数组中出现必然大于 len/2。因此，众数出现的次数必然大于其他所有数字出现次数的和。我们使用动态规划的思想，先记录当前数字与当前数字的出现频率，若下一个数字与当前数字一致则频率加 1，否则频率减 1。当前数字的频率为 0 时，我们将更新当前数字。时间复杂度为 O(n)。
int majorityElement(vector<int>& nums) {
int num = nums[0], count = 1;
for (int i = 1; i < nums.size(); ++i) {
if (nums[i] == num) {
++count;
} else {
--count;
}
if (count == 0) {
num = nums[i];
count = 1;
}
}
return num;
}
解法 4: 分治法
此题的重点解法，具体思想与数组法一致，不同点在于运用了二分的思想来统计当前数字与出现频率。时间复杂度为 O(n)。
int majorityElement(vector<int>& nums) {
return majorityElement(nums, 0, nums.size()-1).first;
}
pair<int, int> majorityElement(vector<int>& nums, int start, int end) {
if (start == end)
return make_pair(nums[start], 1);
int middle = (start + end) / 2;
pair<int, int> left = majorityElement(nums, start, middle);
pair<int, int> right = majorityElement(nums, middle+1, end);
if (left.first == right.first)
return make_pair(left.first, left.second+right.second);
else if (left.second < right.second)
return make_pair(right.first, right.second-left.second);
else if (left.second > right.second)
return make_pair(left.first, left.second-right.second);
else
return make_pair(0, 0);
}
74. 搜索二维矩阵(Search a 2D Matrix)
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。
示例 1:
输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
输出: true
示例 2:
输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
输出: false
解题思路:
由于最近比较忙，所以选了一些不太难的题目来解。在这道题中，我们首先通过二分查找确定目标数字所在的行，然后再在该行中用二分查找目标元素。在原理上是非常简单的，这里就特别提一下一些细节的地方。首先，我们第一次用二分查找的是第一个元素小于等于目标元素的行，因此二分查找的条件应该设为 start < end，这能保证跳出循环后 start 的值不会导致数组越界。而为了满足该行第一个元素小于等于目标元素，我们还需要判定是否需要对 start 进行减 1。但是为了保证 start-1 的值大于等于 0，所以在程序最开头需要加上 matrix[0][0] > target 的判断。算法的时间复杂度为 O((m+n)/2)，具体代码如下:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty() || matrix[0].empty())
return false;
if (matrix[0][0] > target)
return false;
int start = 0, end = matrix.size() - 1, middle = 0;
while (start < end) {
middle = (start + end) / 2;
if (matrix[middle][0] == target) {
return true;
} else if (matrix[middle][0] < target) {
start = middle + 1;
} else {
end = middle - 1;
}
}
int entry = (matrix[start][0] > target) ? start - 1 : start;
start = 0, end = matrix[entry].size() - 1;
while (start <= end) {
middle = (start + end) / 2;
if (matrix[entry][middle] == target) {
return true;
} else if (matrix[entry][middle] < target) {
start = middle + 1;
} else {
end = middle - 1;
}
}
return false;
}
另外，也分享一种参考得来的 O(m+n) 的算法，该算法的优点是代码比较简洁:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int rows = matrix.size();
if (rows <= 0)
return false;
int cols = matrix[0].size();
int row = 0, col = cols-1;
while (row >= 0 && row < rows && col >= 0 && col < cols) {
int val = matrix[row][col];
if (val == target)
return true;
else if (val < target)
++row;
else
--col;
}
return false;
}
240. 搜索二维矩阵 II(Search a 2D Matrix II)
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例:
现有矩阵 matrix 如下：
[
[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。
解题思路:
这道题是上一题的一个升级版，虽然题目的标签里有分治算法，但是我并没有找到比较好的分治算法来解决这个问题。其实这道题的解法可以参考上一道题，其中，时间复杂度为 O(m+n) 具体代码如下:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty() || matrix[0].empty())
return false;
int rows = matrix.size(), cols = matrix[0].size();
int r = 0, c = cols - 1;
while (r < rows && c >= 0) {
if (matrix[r][c] == target)
return true;
else if (matrix[r][c] < target)
++r;
else
--c;
}
return false;
}
根据题目的定义，使用以下的例子来解释我们的算法:
现有矩阵 matrix 如下：
[
[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 = 13。
首先，我们从矩阵的右上角开始遍历，我们发现当前元素 15 的值大于目标值 13，且外，我们可以确保与 15 处于同一列的其他元素都大于 13。因此，我们可以将最后一列从矩阵中删去。
[
[1, 4, 7, 11],
[2, 5, 8, 12],
[3, 6, 9, 16],
[10, 13, 14, 17],
[18, 21, 23, 26]
]
之后，我们的当前元素变为 11，我们发现 11 小于目标值，且外，我们可以确保与 11 处于同一行的其他元素都小于 13，因此，我们可以将第一列从矩阵中删去。
[
[2, 5, 8, 12],
[3, 6, 9, 16],
[10, 13, 14, 17],
[18, 21, 23, 26]
]
当前元素变为 12，由于 12 小于目标值，我们采用与第二步相同的策略。
[
[3, 6, 9, 16],
[10, 13, 14, 17],
[18, 21, 23, 26]
]
当前元素变为 16，由于 16 大于目标值，我们采用与第一步相同的策略。
[
[3, 6, 9],
[10, 13, 14],
[18, 21, 23]
]
当前元素变为 9，由于 9 小于目标值，我们采用与第二步相同的策略。
[
[10, 13, 14],
[18, 21, 23]
]
当前元素变为 14，由于 14 大于目标值，我们采用与第一步相同的策略。
[
[10, 13],
[18, 21]
]
当前元素变为 13，我们成功查找到了目标值，返回 true。