文章目录
- 一、二维数组中的查找（leetcode 240）
- 二、旋转数组的最小数字（leetcode 153）
- 三、旋转数组中的查找（leetcode 33）
- 四、数组中出现次数超过一半的数字（leetcode 169）
- 五、把数组排成最大的数（leetcode 179）
- 六、数组中只出现一次的数字（leetcode 136）
- 七、排序数组中查找某一个数第一次和最后一次出现的位置（leetcode 34）
- 八、寻找数组中的重复元素（leetcode 287）
- 九、顺时针打印矩阵（leetcode 54）
- 十、数组中第K大的数（leetcode 215）
- 十一、数据流中的中位数（leetcode 295）
- 十二、接雨水问题（leetcode 42）
- 十三、求两个数组的交集（leetcode 350）
- 十四、二维数组的最长递增序列（leetcode 329）
- 十五、两个排序数组找第K大的数（leetcode 4）
- 十六、调整数组使所有奇数位于偶数前面（剑指offer）
- 十七、二维矩阵顺时针旋转90度（leetcode 48）
- 十八、包含重复元素的数组全排列
一、二维数组中的查找（leetcode 240）
思路：如果当前元素大于目标值，则向左移动列，如果当前元素小于目标值，则向下移动行。
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty())
return false;
int col_len = matrix[0].size(), row_len = matrix.size();
int row = 0, col = col_len - 1;
// 循环条件为行和列的作用范围
while (row < row_len && col >= 0){
if (matrix[row][col] == target)
return true;
// 如果当前元素大于目标值，则向左移动列
else if (matrix[row][col] > target)
col--;
// 如果当前元素小于目标值，则向下移动行
else
row++;
}
return false;
}
};二、旋转数组的最小数字（leetcode 153）
思路：二分查找，如果中间位置的值比左边元素大，则更新左边元素位置为中间位置，否则更新右边元素位置为中间位置。
class Solution {
public:
int findMin(vector<int>& nums) {
int low = 0, high = nums.size()-1, mid = 0;
while (nums[low] > nums[high]){
if (high - low == 1){
mid = high;
break;
}
mid = low + (high - low) / 2;
// 二分查找，如果中间位置的值比左边元素大，则更新左边元素位置为中间位置
// 否则更新右边元素位置为中间位置
if (nums[mid] > nums[low])
low = mid;
else
high = mid;
}
return nums[mid];
}
};三、旋转数组中的查找（leetcode 33）
思路：
对于[0,1,2,3,4,5,6,7]而言，如红色标出所示，如果nums[mid]<nums[right]，即中间的数小于最右边的数，那么mid（包括mid）右边的数是有序的，如果中间的数大于最右边的数，那么mid（包括mid）左边的数是有序的。那我们每次都可以折半查找。
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size()-1;
while (left <= right){
int mid = left + (right - left) / 2;
if (nums[mid] == target)
return mid;
// 如果中间数比右边数小，则右半边是有序的
if (nums[mid] < nums[right]){
// 如果target在右半边范围内，则进行二分查找
if (nums[mid] < target && target <= nums[right])
left = mid + 1;
// 如果target不在右边范围，则缩小查找区间
else
right = mid - 1;
}
// 否则左半边是有序的
else{
// 如果target在左半边范围内，则进行二分查找
if (nums[left] <= target && target < nums[mid])
right = mid - 1;
// 如果target不在左边范围，则缩小查找区间
else
left = mid + 1;
}
}
return -1;
}
};四、数组中出现次数超过一半的数字（leetcode 169）
思路：题目中要找的数字出现的次数超过数组长度的一半，也就是说它出现的次数比其他所有数字出现的次数的和还要多。因此我们可以考虑在遍历数组的时候保存两个值：一个是数组中的一个数字，一个是次数。
第一个数字作为士兵，防守阵地(cnt = 1)；
遇到相同的元素，cnt++；
如果cnt == 0时，选取新的下标值对应的元素作为防守阵地的士兵；
遇到不同的元素（即为敌人），同归于尽，cnt–；
最后留在阵地上的士兵，可能是主元素。
class Solution {
public:
int majorityElement(vector<int>& nums) {
int result = nums[0], count = 1, len = nums.size();
for(int i = 1; i < len; ++i)
{
if(nums[i] == result)
count++;
else if(count == 0)
{
result = nums[i];
count = 1;
}
else
count --;
}
return result;
}
};五、把数组排成最大的数（leetcode 179）
思路：重新定义排序规则，两个数字m和n能够拼接成mn和nm，如果mn大于nm，则m应该排在n前面；如果mn小于nm，则m应该排在n后面。
class Solution {
public:
string largestNumber(vector<int>& nums) {
vector<string> vec_str;
for (auto num : nums)
vec_str.push_back(to_string(num));
sort(vec_str.begin(), vec_str.end(), [](const string & str1, const string & str2)->bool{
return str1 + str2 > str2 + str1;
});
string res;
for (auto str : vec_str)
res.append(str);
if (res[0] == '0')
return "0";
return res;
}
};六、数组中只出现一次的数字（leetcode 136）
思路：利用异或的基本性质（相同为0，相异为1，与0异或等于本身），以及交换律和结合律。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = nums[0], sz = nums.size();
for (int i = 1; i < sz; ++i){
res ^= nums[i];
}
return res;
}
};七、排序数组中查找某一个数第一次和最后一次出现的位置（leetcode 34）
思路：二分查找的变式，注意边界条件。
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int low = lower_bound(nums, target);
int high = upper_bound(nums, target);
if (nums.empty() || nums[low] != target)
return vector<int>{-1, -1};
else
return vector<int>{low, high};
}
// 查找第一次出现的位置
int lower_bound(vector<int>& nums, int target){
int low = 0, high = nums.size() - 1;
while (low < high){
int mid = low + (high - low) / 2;
if (nums[mid] >= target)
high = mid;
else
low = mid + 1;
}
return low;
}
// 查找最后一次出现的位置
int upper_bound(vector<int>& nums, int target){
int low = 0, high = nums.size() - 1;
while (low <= high){
int mid = low + (high - low) / 2;
if (nums[mid] <= target)
low = mid + 1;
else
high = mid - 1;
}
return high;
}
};八、寻找数组中的重复元素（leetcode 287）
思路：用哈希表存储每一个元素出现的次数。
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int res;
unordered_map<int, int> ump;
for (auto num : nums){
ump[num]++;
if (ump[num] > 1){
res = num;
break;
}
}
return res;
}
};九、顺时针打印矩阵（leetcode 54）
思路：用四个变量记录下边界，然后分析打印每一步的前提条件。
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> res;
if (matrix.empty())
return res;
// 用四个变量记录下边界
int top = 0, btm = matrix.size()-1, left = 0, right = matrix[0].size()-1;
while (left <= right && top <= btm){
// 打印第一步不需要条件
for (int j = left; j <= right; ++j){
res.push_back(matrix[top][j]);
}
// 打印第二步的前提条件是(top<btm)
if (top < btm){
for (int i = top+1; i <= btm; ++i){
res.push_back(matrix[i][right]);
}
}
// 打印第三步的前提条件是(top<btm && left<right)
if (top < btm && left < right){
for (int j = right-1; j >= left; --j){
res.push_back(matrix[btm][j]);
}
}
// 打印第四步的前提条件是(top+1<btm&&left<right)
if (left < right && top+1 < btm){
for (int i = btm-1; i >= top+1; --i){
res.push_back(matrix[i][left]);
}
}
++top, ++left, --btm, --right;
}
return res;
}
};十、数组中第K大的数（leetcode 215）
思路：基于快排的思想，比较k和mid的位置关系，每次只需要利用一个区间即可。
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
quick_sort(nums, 0, nums.size()-1, k);
return nums[nums.size() - k];
}
void quick_sort(vector<int>& nums, int low, int high, int k){
if (low < high){
int mid = partition(nums, low, high);
// 比较k和mid的位置关系，每次只需要利用一个区间即可
if (mid > nums.size() - k)
quick_sort(nums, 0, mid - 1, k);
else if (mid < nums.size() - k)
quick_sort(nums, mid + 1, high, k);
else
return;
}
}
// 根据枢纽元划分左右区间
int partition(vector<int>& nums, int low, int high){
int pivot = nums[low], mid = low;
for (int i = low + 1; i <= high; ++i)
if (nums[i] <= pivot)
swap(nums[i], nums[++mid]);
swap(nums[low], nums[mid]);
return mid;
}
};十一、数据流中的中位数（leetcode 295）
思路：基于最大堆和最小堆来实现，新元素先加入到最大堆，然后将最大堆的堆顶元素加入最小堆中并弹出，这样保证了最小堆的堆顶元素永远大于最大堆的堆顶元素。如果最小堆的元素个数大于最大堆的元素个数，则继续弹出和加入操作，保证最大堆的元素个数始终与最小堆的元素个数相差不超过1。
class MedianFinder {
public:
priority_queue<int, vector<int>, less<int>> large; // 定义最大堆
priority_queue<int, vector<int>, greater<int>> small; // 定义最小堆
MedianFinder() { }
void addNum(int num) {
// 保证最小堆的堆顶元素永远大于最大堆的堆顶元素
large.push(num);
small.push(large.top());
large.pop();
if (small.size() > large.size()){
// 保证最大堆的堆顶元素永远小于最小堆的堆顶元素
large.push(small.top());
small.pop();
}
}
double findMedian() {
return large.size() > small.size() ?
large.top() : 0.5 * (small.top() + large.top());
}
};十二、接雨水问题（leetcode 42）
思路：保存一个左指针left，右指针right，以及左指针遍历的最大值maxleft以及右指针遍历的最大值maxright。如果当前高度小于maxleft，说明有坑，需要补全，对于right也是一样，但是要保持height[left] < height[right]，目的是找到最高点。
class Solution {
public:
int trap(vector<int>& height) {
if (height.size() == 0) return 0;
int left = 0, right = height.size() - 1, maxleft = 0, maxright = 0, res = 0;
while (left < right) {
if (height[left] < height[right]){
maxleft = max(maxleft, height[left]);
res += maxleft - height[left];
left++;
} else {
maxright = max(maxright, height[right]);
res += maxright - height[right];
right--;
}
}
return res;
}
};十三、求两个数组的交集（leetcode 350）
思路：用哈希表记录下较长的数组中的每个元素及其出现的次数，遍历较短长度的数组，如果能找到则递减计数。
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
vector<int> res;
if (nums1.size() < nums2.size())
swap(nums1, nums2);
unordered_map<int, int> mp;
// 用哈希表记录下较长的数组中的每个元素及其出现的次数
for (int i = 0; i < nums1.size(); ++i)
mp[nums1[i]]++;
for (auto num : nums2){
if (mp.find(num) != mp.end() && mp[num] > 0){
res.push_back(num);
mp[num]--;
}
}
return res;
}
};十四、二维数组的最长递增序列（leetcode 329）
思路：深度优先搜索+记忆化搜索，具体方法如下：从起点开始遍历矩阵，递归寻找其最长递增路径。定义辅助数组record，用于记录已经搜索过的矩阵元素的数据，如record[x][y]存储了从坐标(x, y)出发的最长递增路径长度。之后，进行深度优先搜索。逐一检查某个元素的四个方向，并继续从所有可能出现最长路径的方向上进行搜索。 当遇到record[x][y]已算出的情况，直接返回record[x][y]，减少运算量。
class Solution {
public:
// record[x][y]存储了从坐标(x, y)出发的最长递增路径长度。
int dfs(vector<vector<int>>& matrix, vector<vector<int>>& record, int x, int y, int lastval) {
if (x < 0 || y < 0 || x >= matrix.size() || y >= matrix[0].size()) return 0;
if (matrix[x][y] > lastval) {
// 路线已算出，直接返回结果
if (record[x][y] != 0) return record[x][y];
// 向四周搜索
int left = dfs(matrix, record, x + 1, y, matrix[x][y]) + 1;
int right = dfs(matrix, record, x - 1, y, matrix[x][y]) + 1;
int top = dfs(matrix, record, x, y + 1, matrix[x][y]) + 1;
int bottom = dfs(matrix, record, x, y - 1, matrix[x][y]) + 1;
record[x][y] = max(left, max(right, max(top, bottom)));
return record[x][y];
}
return 0;
}
int longestIncreasingPath(vector<vector<int>>& matrix) {
if (matrix.size() == 0) return 0;
int res = 0;
vector<vector<int>> record(matrix.size(), vector<int>(matrix[0].size(), 0));
for (int i = 0; i < matrix.size(); ++i) {
for (int j = 0; j < matrix[0].size(); ++j) {
res = max(res, dfs(matrix, record, i, j, -1));
}
}
return res;
}
};十五、两个排序数组找第K大的数（leetcode 4）
思路：比较这两个数组的第 K/2 小的数字的大小，如果第一个数组的第 K/2 个数字较小的话，那么说明我们要找的数字肯定不在 nums1 中的前 K/2 个数字，所以我们可以将其淘汰，将 nums1 的起始位置向后移动 K/2 个，并且此时的K也自减去 K/2，调用递归。
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
return (findKth(nums1, nums2, (m + n + 1) / 2) + findKth(nums1, nums2, (m + n + 2) / 2)) / 2.0;
}
int findKth(vector<int> nums1, vector<int> nums2, int k) {
if (nums1.empty()) return nums2[k - 1];
if (nums2.empty()) return nums1[k - 1];
if (k == 1) return min(nums1[0], nums2[0]);
int i = min((int)nums1.size(), k / 2), j = min((int)nums2.size(), k / 2);
if (nums1[i - 1] > nums2[j - 1]) {
return findKth(nums1, vector<int>(nums2.begin() + j, nums2.end()), k - j);
} else {
return findKth(vector<int>(nums1.begin() + i, nums1.end()), nums2, k - i);
}
return 0;
}
};十六、调整数组使所有奇数位于偶数前面（剑指offer）
思路：解法一是利用冒泡排序的方法，遇到前偶后奇就交换；解法二是空间换时间的做法，先摘取再合并。
// 解法一
class Solution {
public:
void reOrderArray(vector<int> &array) {
// 类似冒泡算法，前偶后奇数就交换
for (int i = 0; i < array.size(); ++i) {
for (int j = array.size()-1; j > i; --j) {
if (array[j] % 2 == 1 && array[j-1] % 2 == 0)
swap(array[j], array[j-1]);
}
}
}
};
// 解法二
class Solution {
public:
void reOrderArray(vector<int> &array) {
vector<int> res;
for(int i = 0; i < array.size(); i++)
{
if(array[i] % 2 == 1)
res.push_back(array[i]);
}
for(int i = 0; i < array.size(); i++)
{
if(array[i] % 2 == 0)
res.push_back(array[i]);
}
array.swap(res);
}
};十七、二维矩阵顺时针旋转90度（leetcode 48）
思路：先求转置，再把每一行反转。
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
/*
* 先求转置再反转每一行
*/
int sz = matrix.size();
for (int i = 0; i < sz; ++i){
for (int j = i+1; j < sz; ++j)
swap(matrix[i][j], matrix[j][i]);
reverse(matrix[i].begin(), matrix[i].end());
}
return;
}
};十八、包含重复元素的数组全排列
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
set<vector<int>> ans; //用set去重
void fun(vector<int> &vec, int start, int len)
{
// 当start==arr.length-1时，说明子序列的长度为1，就不用再往下划分子序列了
if (start == len)
ans.insert(vec);
for (int i = start; i < len; i++)
{
swap(vec[start], vec[i]);
fun(vec, start + 1, len);
swap(vec[start], vec[i]);
}
}
vector<vector<int>> Permutation(vector<int> vec) {
vector<vector<int>> vecout;
if (!vec.empty())
{
fun(vec, 0, vec.size());
for (auto tmp : ans)
vecout.push_back(tmp);
}
return vecout;
}
int main() {
vector<vector<int>> res = Permutation({ 1, 2, 3 });
for (int i = 0; i < res.size(); ++i) {
for (int j = 0; j < res[0].size(); ++j) {
cout << res[i][j] << " ";
}
cout << endl;
}
system("pause");
return 0;
}