当前位置：首页 > news >正文

东莞企业网站建设营销山东百度推广

news 2026/4/7 6:48:39

东莞企业网站建设营销,山东百度推广,品牌建设发展规划,免费开发游戏作者推荐 [二分查找]LeetCode2040:两个有序数组的第 K 小乘积本文涉及的基础知识点二分查找算法合集分组动态规划题目给你一个下标从 0 开始包含 n 个正整数的数组 arr ，和一个正整数 k 。如果对于每个满足 k < i < n-1 的下标 i ，都有…

作者推荐

[二分查找]LeetCode2040:两个有序数组的第 K 小乘积

本文涉及的基础知识点

二分查找算法合集
分组动态规划

题目

给你一个下标从 0 开始包含 n 个正整数的数组 arr ，和一个正整数 k 。
如果对于每个满足 k <= i <= n-1 的下标 i ，都有 arr[i-k] <= arr[i] ，那么我们称 arr 是 K 递增的。
比方说，arr = [4, 1, 5, 2, 6, 2] 对于 k = 2 是 K 递增的，因为：
arr[0] <= arr[2] (4 <= 5)
arr[1] <= arr[3] (1 <= 2)
arr[2] <= arr[4] (5 <= 6)
arr[3] <= arr[5] (2 <= 2)
但是，相同的数组 arr 对于 k = 1 不是 K 递增的（因为 arr[0] > arr[1]），对于 k = 3 也不是 K 递增的（因为 arr[0] > arr[3] ）。
每一次操作中，你可以选择一个下标 i 并将 arr[i] 改成任意正整数。
请你返回对于给定的 k ，使数组变成 K 递增的最少操作次数。
示例 1：
输入：arr = [5,4,3,2,1], k = 1
输出：4
解释：
对于 k = 1 ，数组最终必须变成非递减的。
可行的 K 递增结果数组为 [5,6,7,8,9]，[1,1,1,1,1]，[2,2,3,4,4] 。它们都需要 4 次操作。
次优解是将数组变成比方说 [6,7,8,9,10] ，因为需要 5 次操作。
显然我们无法使用少于 4 次操作将数组变成 K 递增的。
示例 2：
输入：arr = [4,1,5,2,6,2], k = 2
输出：0
解释：
这是题目描述中的例子。
对于每个满足 2 <= i <= 5 的下标 i ，有 arr[i-2] <= arr[i] 。
由于给定数组已经是 K 递增的，我们不需要进行任何操作。
示例 3：
输入：arr = [4,1,5,2,6,2], k = 3
输出：2
解释：
下标 3 和 5 是仅有的 3 <= i <= 5 且不满足 arr[i-3] <= arr[i] 的下标。
将数组变成 K 递增的方法之一是将 arr[3] 变为 4 ，且将 arr[5] 变成 5 。
数组变为 [4,1,5,4,6,5] 。
可能有其他方法将数组变为 K 递增的，但没有任何一种方法需要的操作次数小于 2 次。
提示：
1 <= arr.length <= 10⁵
1 <= arr[i], k <= arr.length

分析

时间复杂度

O(nlogn)，枚举每个元素，时间复杂度O(n)，每个元素二分查找O(logn)。

代码

原理

一，有多少对不符合递增，则至少需要多少次操作。arr[i]和arr[i+1]不符合，需要修改arr[i]或arr[i+1]。能否一次修改，同时解决两个数对，假定arr[i-1] > arr[i] > arr[i+1]，由于arr[i-1]>arr[i+1]，所以arr[i]无论如何都不可能大于等于arr[i-1]，同时小于等于arr[i+1]。
二，需要的操作数，可能大于非递增的对数。比如：4 1 3 ，4 1非递增，1 3递增。
三，操作次数等于=总元素数-最长递增序列的长度。假定最长子系列为：newNew[0]…newNew[n]。
四，第三只能说明是一个解，现在来证明是最优解：假定arr2最优解，删掉修改过的元素，那么它一定是arr的子序列，且是递增的。此子系列越长，删除（操作）的元素越少。


newNew[0]之前的元素	全部改成newNew[0]
newNew[n]之后的元素	全部改成newNew[n]
newNew[i]和newNew[i+1]的元素	全改成newNew[i]

变量解释


vLenMinEnd	vLenMinEnd[i]=x，在长度为i的子序列中，结尾的最小值为x

核心代码

class Solution {
public:int kIncreasing(vector<int>& arr, int k) {int iMaxLen = 0;for (int i = 0; i < k; i++){vector<int> vLenMinEnd = { 0,arr[i] };for (int j = i + k; j < arr.size(); j += k){auto index = std::upper_bound(vLenMinEnd.begin(), vLenMinEnd.end(), arr[j])- vLenMinEnd.begin();if (index >= vLenMinEnd.size()){vLenMinEnd.emplace_back(arr[j]);continue;}vLenMinEnd[index] = min(vLenMinEnd[index], arr[j]);		}iMaxLen += vLenMinEnd.size() - 1;}return arr.size()-iMaxLen;}
};

测试用例

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
assert(v1[i] == v2[i]);
}
}

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}

int main()
{
vector arr;
int k, res;
{
Solution slu;
arr = { 12, 6, 12, 6, 14, 2, 13, 17, 3, 8, 11, 7, 4, 11, 18, 8, 8, 3 }, k = 1;
auto res = slu.kIncreasing(arr, k);
Assert(12, res);
}
{
Solution slu;
arr = { 5, 4, 3, 2, 1 }, k = 1;
auto res = slu.kIncreasing(arr,k);
Assert(4, res);
}
{
Solution slu;
arr = { 4,1,5,2,6,2 }, k = 2;
auto res = slu.kIncreasing(arr, k);
Assert(0, res);
}
{
Solution slu;
arr = { 4,1,5,2,6,2 }, k = 3;
auto res = slu.kIncreasing(arr, k);
Assert(2, res);
}

//CConsole::Out(res);

}

2023年9月旧代码

class Solution {
public:
int kIncreasing(vector& arr, int k) {
vector<vector> vSubArr(k);
for (int i = 0; i < arr.size(); i++)
{
vSubArr[i%k].push_back(arr[i]);
}
int iRet = 0;
for ( auto& v : vSubArr)
{
iRet += NeedChange(v, 0, v.size() );
}
return iRet;
}
int NeedChange(vector& arr,int iLeft,int iRight)
{
std::map<int, int> mValueNums;
for (const auto& a : arr)
{
auto it = mValueNums.upper_bound(a);
auto itTmp = it;
const int iValue = ((mValueNums.begin() == it) ? 0 : (–itTmp)->second) + 1;
if ((mValueNums.end() != it) && (it->second <= iValue))
{
mValueNums.erase(it);
}
mValueNums[a] = iValue;
}
return arr.size() - mValueNums.rbegin()->second;
}
int m_iK;
};

2023年9月第一版

class Solution {
public:
int kIncreasing(vector& arr, int k) {
int iRet = 0;
for (int turn = 0; turn < k; turn++)
{
std::map<int, int> mEndLen;
mEndLen[0] = 0;
int iMaxLen = 0;
for (int index = turn; index < arr.size(); index += k)
{
auto it = mEndLen.upper_bound(arr[index]);
const int iLen = std::prev(it)->second+1;
it = mEndLen.lower_bound(arr[index]);
auto ij = it;
for (; (ij != mEndLen.end()) && (ij->second <= iLen); ij++);
mEndLen.erase(it, ij);
mEndLen[arr[index]] = iLen;
iMaxLen = max(iMaxLen, iLen);
}
iRet += iMaxLen;
}
return arr.size()- iRet;
}
};

2023年9月第二版

class Solution {
public:
int kIncreasing(vector& arr, int k) {
int iRet = 0;
for (int turn = 0; turn < k; turn++)
{
vector vValue;
for (int index = turn; index < arr.size(); index += k)
{
auto it = std::upper_bound(vValue.begin(), vValue.end(),arr[index]);
if (vValue.end() == it)
{
vValue.emplace_back(arr[index]);
}
else
{
*it = arr[index];
}
}
iRet += vValue.size();
}
return arr.size()- iRet;
}
};