☘️☘️☘️规模为n的原问题的解无法直接求出,进行问题规模缩减,划分子问题(这里子问题相互独立而且和原问题解的性质是相同的,只是问题规模缩小了)。如果子问题的规模仍然不够小,再进行子问题划分,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止,最后求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原问题的解。
分治算法所能解决的问题一般具有以下几个特征:
经典例题如下:
题目描述:给定一个包含红色、白色和蓝色、共 n
个元素的数组 nums
,原地 对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
我们使用整数 0
、 1
和 2
分别表示红色、白色和蓝色。
思路: 三指针,用 i 来遍历数组,left 标记 0 区域的最右侧,right 标记 2 区域的最左侧
然后分类讨论,对于nums[ i ]. 如果为 0,则 swap(nums[++left],nums[ i++ ]) 这里 i++原因是因为交换后的数已经被扫描过了 如果为 1,则 i++. 如果为 2,则 swap(nums[--right],nums[ i ]) 注:由于下标从0开始,那么对于left应该初始化为-1
class Solution {
public:
void sortColors(vector<int>& nums) {
int n = nums.size();
int l = -1, r = n, i = 0;
while (i < r)
{
if (nums[i] == 0)swap(nums[++l], nums[i++]);
else if (nums[i] == 1) i++;
else if (nums[i] == 2) swap(nums[--r], nums[i]);
}
}
};
给你一个整数数组 nums
,请你将该数组升序排列。
方法一:(数组分两块)
思路: 找个基准值,把一个大数组分成两个小数组
class Solution {
public:
void QuickSort(vector<int>& q, int l, int r)
{
if (l >= r) return;
int x = q[l + r >> 1];
int i = l - 1, j = r + 1;
while (i < j)
{
do i++; while (q[i] < x);
do j--; while (q[j] > x);
if (i < j)swap(q[i], q[j]);
}
QuickSort(q, l, j);
QuickSort(q, j + 1, r);
}
vector<int> sortArray(vector<int>& nums) {
auto q = nums;
int n = nums.size();
QuickSort(q, 0, n - 1);
return q;
}
};
方法二:数组分三块 + 随机选择基准元素
思路:数组分三块 + 随机选择基准元素
class Solution {
public:
int getRandom(vector<int>& nums, int left, int right) {
int k = rand();
return nums[k % (right - left + 1) + left];
}
vector<int> sortArray(vector<int>& nums)
{
srand(time(NULL));
QuickSort(nums, 0, nums.size() - 1);
return nums;
}
void QuickSort(vector<int>& nums, int l, int r)
{
if (l >= r) return;
int k = getRandom(nums, l, r);
int i = l, left = l - 1, right = r + 1;
while (i < right)
{
if (nums[i] < k) swap(nums[++left], nums[i++]);
else if (nums[i] == k) i++;
else swap(nums[--right], nums[i]);
}
QuickSort(nums, l, left);
QuickSort(nums, right, r);
}
};
题目描述:给定整数数组 nums
和整数 k
,请返回数组中第 k
个最大的元素。
请注意,你需要找的是数组排序后的第 k
个最大的元素,而不是第 k
个不同的元素。
思路:数组分三块 + 选择基准元素
class Solution {
public:
int sort(vector<int>& nums, int l,int r, int k)
{
if (l == r) return nums[l];
// 1. 找基准元素
int key = nums[l + r >> 1];
// 2. 根据基准元素把数组分三块
int i = l, left = l - 1, right = r + 1;
while (i < right)
{
if (nums[i] < key) swap(nums[++left], nums[i++]]);
else if (nums[i] == key) i++;
else swap(nums[--right], nums[i]);
}
// 3. 分情况讨论
int c = r - right + 1, b = right - left - 1;
if (c >= k) return sort(nums, right, r, k);
else if (b + c >= k) return key;
else return sort(nums, l, left, k - b - c);
}
int findKthLargest(vector<int>& nums, int k) {
return sort(nums, 0, nums.size() - 1,k);
}
};
题目描述:仓库管理员以数组 stock
形式记录商品库存表,其中 stock[i]
表示对应商品库存余量。请返回库存余量最少的 cnt
个商品余量,返回 顺序不限。
思路: 该题目本质就是求数组的最小 k 个元素
class Solution {
public:
void sort(vector<int>& nums, int l, int r, int k) {
if (l >= r) return;
// 1. 基准元素 + 数组分块
int key = nums[l + r >> 1];
int left = l - 1, right = r + 1, i = l;
while (i < right)
{
if (nums[i] < key) swap(nums[++left], nums[i++]);
else if (nums[i] == key) i++;
else swap(nums[--right], nums[i]);
}
// 2. 分情况讨论
int a = left - l + 1, b = right - left - 1;
if (a > k) sort(nums, l, left, k);
else if (a + b >= k) return;
else sort(nums, right, r, k - a - b);
}
vector<int> inventoryManagement(vector<int>& stock, int cnt) {
sort(stock, 0, stock.size() - 1, cnt);
return { stock.begin(),stock.begin() + cnt };
}
};
class Solution {
public:
int tmp[100005];
void mergesort(vector<int>& nums, int l, int r){
if (l >= r) return;
// 1. 根据中间元素,划分区间
int mid = l + r >> 1;
// 2. 处理左右两部分
mergesort(nums, l, mid), mergesort(nums, mid + 1, r);
// 3. 处理一左一右情况
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
{
if (nums[i] <= nums[j]) tmp[k++] = nums[i++];
else tmp[k++] = nums[j++];
}
// 4. 处理剩下排序过程
while (i <= mid) tmp[k++] = nums[i++];
while (j <= r) tmp[k++] = nums[j++];
// 5. 更新原数组
for (i = l, j = 0; i <= r; i++, j++) nums[i] = tmp[j];
}
vector<int> sortArray(vector<int>& nums) {
int n = nums.size();
mergesort(nums, 0, n - 1);
return nums;
}
};
题目描述:在股票交易中,如果前一天的股价高于后一天的股价,则可以认为存在一个「交易逆序对」。请设计一个程序,输入一段时间内的股票交易记录 record
,返回其中存在的「交易逆序对」总数。
对于数列的第 i 个和第 j 个元素,如果满足 i < j 且 a[i] > a[j],则其为一个逆序对。 重要的地方在于,一个元素可以不只是在一个逆序对中存在。如果 k > j > i 且 a[i] > a[j] > a[k],那么这里 有两个含 a[i] 的逆序对,分别是 (a[i], a[j]) 和 (a[i], a[k]), a[i]是可以使用多次的。 那么第二步是分析问题,这里我们可以使用分治法解决问题。 我们将序列从中间分开,将逆序对分成三类:
因此这就是我们算法的大致框架: 计算逆序对的数量(序列): 1. 递归算左边的; 2. 递归算右边的; 3. 算一个左一个右的; 4. 把他们加到到一起。
class Solution {
public:
int tmp[100005];
int mergesort(vector<int>& nums, int l, int r)
{
if (l >= r) return 0;
int mid = l + r >> 1;
int res = mergesort(nums, l, mid) + mergesort(nums, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
{
if (nums[i] <= nums[j]) tmp[k++] = nums[i++];
else {
tmp[k++] = nums[j++];
res += mid - i + 1; //区间内逆序数目
}
}
while (i <= mid) tmp[k++] = nums[i++];
while (j <= r) tmp[k++] = nums[j++];
for (i = l, j = 0; i <= r; i++, j++) nums[i] = tmp[j];
return res;
}
int reversePairs(vector<int>& record) {
return mergesort(record, 0, record.size() - 1);
}
};
给你一个整数数组 nums
,按要求返回一个新数组 counts
。数组 counts
有该性质: counts[i]
的值是 nums[i]
右侧小于 nums[i]
的元素的数量。
思路:该题与上题算逆序对数目类似,需要用个数组来存 nums 的下标 当前元素后面,有多少个比我小。(降序)
class Solution {
public:
int tmpNums[500005];
int tmpIndex[500005];
vector<int> ret;
vector<int> index; //记录nums 当前元素的原始下标
void mergesort(vector<int>& nums, int l, int r) {
if (l >= r) return;
// 1. 根据中间元素,划分区间
int mid = l + r >> 1;
// 2. 处理左右两部分
mergesort(nums, l, mid), mergesort(nums, mid + 1, r);
// 3. 处理一左一右情况
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
{
if (nums[i] <= nums[j]) {
tmpIndex[k] = index[j];
tmpNums[k++] = nums[j++];
}
else {
ret[index[i]] += r - j + 1;
tmpIndex[k] = index[i];
tmpNums[k++] = nums[i++];
}
}
// 4. 处理剩下排序过程
while (i <= mid) {
tmpIndex[k] = index[i];
tmpNums[k++] = nums[i++];
}
while (j <= r) {
tmpIndex[k] = index[j];
tmpNums[k++] = nums[j++];
}
// 5. 更新原数组
for (i = l, j = 0; i <= r; i++, j++) {
index[i] = tmpIndex[j];
nums[i] = tmpNums[j];
}
}
vector<int> countSmaller(vector<int>& nums) {
int n = nums.size();
ret.resize(n);
index.resize(n);
// 初始化一下 index 数组
for (int i = 0; i < n; i++) index[i] = i;
mergesort(nums, 0, n - 1);
return ret;
}
};
给定一个数组 nums
,如果 i < j
且 nums[i] > 2*nums[j]
我们就将 (i, j)
称作一个重要翻转对。
思路: 方法一(降序): 找当前元素后面,有多少元素的两倍比我小,res += r - j + 1; 方法二(升序): 找当前元素之前,有多少元素的一半比我大 res += mid - i + 1;
方法一:
class Solution {
public:
int tmp[100005];
int mergesort(vector<int>& nums, int l, int r)
{
if (l >= r) return 0;
// 1. 根据左右元素划分区间
int mid = (r + l) >> 1;
// 2. 计算左右两侧翻转对
int res = mergesort(nums, l, mid) + mergesort(nums, mid + 1, r);
// 3. 先计算翻转对数量
int i = l, j = mid + 1;
while (i <= mid) //降序的情况
{
if (j <= r && nums[j] >= nums[i] / 2.0) j++;
if (j > r) break;
res += r - j + 1;
i++;
}
// 4. 合并有序数组
i = l, j = mid + 1;
int k = l;
while (i <= mid && j <= r)
{
if (nums[i] <= nums[j]) tmp[k++] = nums[j++];
else tmp[k++] = nums[i++];
}
while (i <= mid) tmp[k++] = nums[i++];
while (j <= r) tmp[k++] = nums[j++];
for (j = l; j <= r; j++) nums[j] = tmp[j];
return res;
}
int reversePairs(vector<int>& nums) {
return mergesort(nums, 0, nums.size() - 1);
}
};
方法二:
class Solution {
public:
int tmp[100005];
int mergesort(vector<int>& nums, int l, int r)
{
if (l >= r) return 0;
// 1. 根据左右元素划分区间
int mid = (r + l) >> 1;
// 2. 计算左右两侧翻转对
int res = mergesort(nums, l, mid) + mergesort(nums, mid + 1, r);
// 3. 先计算翻转对数量
int i = l, j = mid + 1;
while (j <= r) //升序的情况
{
while (i <= mid && nums[j] >= nums[i] / 2.0) i++;
if (i > mid) break;
res += mid - i + 1;
j++;
}
// 4. 合并有序数组
i = l, j = mid + 1;
int k = 0;
while (i <= mid && j <= r)
{
if (nums[i] <= nums[j]) tmp[k++] = nums[i++];
else tmp[k++] = nums[j++];
}
while (i <= mid) tmp[k++] = nums[i++];
while (j <= r) tmp[k++] = nums[j++];
for (i = l, j = 0; i <= r; i++, j++) nums[i] = tmp[j];
return res;
}
int reversePairs(vector<int>& nums) {
return mergesort(nums, 0, nums.size() - 1);
}
};