手机网站跳出率低,做景观要用的植物网站,新浪云平台创建wordpress,网站开发部门的规章制度本文涉及的基础知识点
二分查找算法合集
作者推荐
动态规划LeetCode2552#xff1a;优化了6版的1324模式
题目
给你一个长度为 2 * n 的整数数组。你需要将 nums 分成 两个 长度为 n 的数组#xff0c;分别求出两个数组的和#xff0c;并 最小化 两个数组和之 差的绝对…本文涉及的基础知识点
二分查找算法合集
作者推荐
动态规划LeetCode2552优化了6版的1324模式
题目
给你一个长度为 2 * n 的整数数组。你需要将 nums 分成 两个 长度为 n 的数组分别求出两个数组的和并 最小化 两个数组和之 差的绝对值 。nums 中每个元素都需要放入两个数组之一。 请你返回 最小 的数组和之差。 示例 1 输入nums [3,9,7,3] 输出2 解释最优分组方案是分成 [3,9] 和 [7,3] 。 数组和之差的绝对值为 abs((3 9) - (7 3)) 2 。 示例 2 输入nums [-36,36] 输出72 解释最优分组方案是分成 [-36] 和 [36] 。 数组和之差的绝对值为 abs((-36) - (36)) 72 。 示例 3 输入nums [2,-1,0,4,-2,-9] 输出0 解释最优分组方案是分成 [2,4,-9] 和 [-1,0,-2] 。 数组和之差的绝对值为 abs((2 4 -9) - (-1 0 -2)) 0 。 参数范围 1 n 15 nums.length 2 * n -107 nums[i] 107
折半查找后二分
时间复杂度
O(2nlog2n)。
变量解释
vLeftvLeft[i]表示从前n个数据中选择i个数的和记录所有可能vRight类似记录的是右边
分析
如果从左边选择i个数那么需要从右边选择n-i个数。假定从左边i个数的和是n1右边选择n-i个数的和为n2。枚举n1从v2中选择第一个大于等于n2的数和第一个小于n2的数。iTotal 是nums的和。 n1n2 iTotal-n1-n2 n2 iTotal/2 - n1 iTotal要分奇数和偶数分别处理。我们将所有数都乘以2,iTotal就必定是偶数了。
注意
不要忘记
v[0].emplace_back(0);代码
核心代码
class Solution {
public:int minimumDifference(vectorint nums) {const int iTotal std::accumulate(nums.begin(), nums.end(), 0);int n nums.size() / 2;vectorvectorint vLeft(n 1), vRight(n 1);auto Build [n](vectorvectorint v,int* p, int len){v[0].emplace_back(0);for (int i 0; i len; i){for (int j n; j 1 ; j--){for (const auto num : v[j - 1]){v[j].emplace_back(num p[i] * 2);}}}};Build(vLeft, nums.data(), n);Build(vRight, nums.data()n, n);int iRet INT_MAX;for (int i 0; i n; i){auto v1 vLeft[i];auto v2 vRight[n - i];sort(v1.begin(), v1.end());sort(v2.begin(), v2.end());for (const auto n1 : v1){auto it std::upper_bound(v2.begin(), v2.end(),iTotal- n1);if (v2.end() ! it){iRet min(iRet, *it n1 - iTotal);}if (v2.begin() ! it){iRet min(iRet, iTotal - n1 - *(std::prev(it)));}}}return iRet;}
};测试用例
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 nums; int res; { nums { 3,9,7,3 }; Solution slu; auto res slu.minimumDifference(nums); Assert(2, res); } { nums { -36,36 }; Solution slu; auto res slu.minimumDifference(nums); Assert(72, res); } { nums { 2,-1,0,4,-2,-9 }; Solution slu; auto res slu.minimumDifference(nums); Assert(0, res); } //CConsole::Out(res);}
2023年2月旧版
class Solution { public: int minimumDifference(vector nums) { m_c nums.size() / 2; vectorstd::unordered_set vSetSumsLeft, vSetSumsRight; std::vector v1( nums.begin(), nums.begin() m_c); CalSumSet(vSetSumsLeft, v1); std::vector v2(nums.begin() m_c, nums.end()); CalSumSet(vSetSumsRight,v2 ); int iTotal std::accumulate(nums.begin(), nums.end(), 0); int iMin INT_MAX; for (int i 0; i m_c; i ) { std::vector v1(vSetSumsLeft[i].begin(), vSetSumsLeft[i].end()); std::vector v2(vSetSumsRight[m_c - i].begin(), vSetSumsRight[m_c - i].end()); std::sort(v1.begin(), v1.end()); std::sort(v2.begin(), v2.end()); auto it v1.begin(); auto ij v2.rbegin(); while ((it ! v1.end()) (ij ! v2.rend())) { int iDiff iTotal - (*it *ij) * 2; iMin min(iMin, abs(iDiff)); if (iDiff 0) { it; } else { ij; } } } return iMin; } static void CalSumSet(vectorstd::unordered_set vSetSums,vector nums) { int c nums.size() ; vSetSums.resize(c 1); vSetSums[0].insert(0); for (const auto n : nums) { vectorstd::unordered_set dp vSetSums; for (int i 0; i c; i) { for (auto it : vSetSums[i]) { dp[i 1].insert(it n); } } vSetSums.swap(dp); } } int m_c;};
扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业
。也就是我们常说的专业的人做专业的事。 | |如果程序是一条龙那算法就是他的是睛|
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境
VS2022 C17
