网站文件夹权限设置,上海网站案例,沈阳网站备案照相,长春网络公司排名本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 给你一个长度为 n 的整数数组 nums 返回使所有数组元素相等需要的最小操作数。
在一次操作中你可以使数组中的一个元素加 1 或者减 1 。
示例 1
输入nums [1,2,3]
输出2
解释
只需要两次操作每次操作指南使一个元素加 1 或减 1
[1,2,3] [2,2,3] [2,2,2]示例 2
输入nums [1,10,2,9]
输出16提示
n nums.length1 nums.length 10^5-10^9 nums[i] 10^9 题目集合
453. 最小操作次数使数组元素相等456. 最小操作次数使数组元素相等 II2448. 使数组相等的最小开销
解法1 数学排序
每次可以将一个数加一或者减一使得所有数组元素相等。凭借直觉可知将所有数组元素向中间靠拢所需要的操作次数最少。下面进行证明。
假设数组元素都变成 x x x 时所需的移动数最少那么 x x x 需要满足什么性质呢
为了简化讨论我们先假定数组长度 n n n 是偶数。我们将数组 nums \textit{nums} nums 从小到大进行排序然后将数组进行首尾配对从而划分为多个数对并将这些数对组成区间 [ nums 0 , nums n − 1 ] , [ nums 1 , nums n − 2 ] , . . . , [ nums n 2 − 1 , nums n 2 ] [\textit{nums}_0, \textit{nums}_{n-1}], [\textit{nums}_1, \textit{nums}_{n-2}], ...,[\textit{nums}_{\frac{n}{2} - 1}, \textit{nums}_{\frac{n}{2}}] [nums0,numsn−1],[nums1,numsn−2],...,[nums2n−1,nums2n] 结论当 x x x 同时位于以上区间内时所需的移动数最少总移动数为 ∑ i 0 n 2 − 1 ( nums n − 1 − i − nums i ) \sum_{i0}^{\frac{n}{2} - 1} (\textit{nums}_{n-1-i} - \textit{nums}_i) i0∑2n−1(numsn−1−i−numsi) 证明对于某一个区间 [ nums i , nums n − 1 − i ] [\textit{nums}_i, \textit{nums}_{n - 1 -i}] [numsi,numsn−1−i] 元素变为 x x x 该区间对应的数对所需要的移动数为 ∣ nums n − 1 − i − x ∣ ∣ nums i − x ∣ ≥ ∣ nums n − 1 − i − x − ( nums i − x ) ∣ nums n − 1 − i − nums i |\textit{nums}_{n - 1 - i} - x| |\textit{nums}_i - x| \ge |\textit{nums}_{n - 1 - i} - x - (\textit{nums}_i - x)| \textit{nums}_{n - 1 - i} - \textit{nums}_i ∣numsn−1−i−x∣∣numsi−x∣≥∣numsn−1−i−x−(numsi−x)∣numsn−1−i−numsi 当且仅当 x ∈ [ nums i , nums n − 1 − i ] x\in [\textit{nums}_i, \textit{nums}_{n - 1 -i}] x∈[numsi,numsn−1−i] 时等号成立。 在上述区间中后一个区间是前一个区间的子集因此只要 x ∈ [ nums n 2 − 1 , nums n 2 ] x \in [\textit{nums}_{\frac{n}{2} - 1}, \textit{nums}_{\frac{n}{2}}] x∈[nums2n−1,nums2n] 就满足要求。 当 n n n 为奇数时我们将排序后的数组中间的元素 nums ⌊ n 2 ⌋ \textit{nums}_{\lfloor \frac{n}{2} \rfloor} nums⌊2n⌋ 当成区间 [ nums ⌊ n 2 ⌋ , nums ⌊ n 2 ⌋ ] [\textit{nums}_{\lfloor \frac{n}{2} \rfloor}, \textit{nums}_{\lfloor \frac{n}{2} \rfloor}] [nums⌊2n⌋,nums⌊2n⌋] 看待则 x ∈ [ nums ⌊ n 2 ⌋ , nums ⌊ n 2 ⌋ ] x \in [\textit{nums}_{\lfloor \frac{n}{2} \rfloor}, \textit{nums}_{\lfloor \frac{n}{2} \rfloor}] x∈[nums⌊2n⌋,nums⌊2n⌋] 即 x nums ⌊ n 2 ⌋ x \textit{nums}_{\lfloor \frac{n}{2} \rfloor} xnums⌊2n⌋ 时所需的移动数最少。
综上所述所有元素都变成 nums ⌊ n 2 ⌋ \textit{nums}_{\lfloor \frac{n}{2} \rfloor} nums⌊2n⌋ 时所需的移动数最少。
class Solution {
public:int minMoves2(vectorint nums) {sort(nums.begin(), nums.end());int n nums.size(), ans 0, x nums[n / 2];for (int i 0; i n; i) ans abs(nums[i] - x);// int i 0, j nums.size() - 1, ans 0;// while (i j) ans nums[j--] nums[i];return ans;}
};复杂度分析
时间复杂度 O ( n log n ) O(n\log n) O(nlogn)其中 n n n 是数组 nums \textit{nums} nums 的长度。排序需要 O ( n log n ) O(n\log n) O(nlogn) 的时间。空间复杂度 O ( log n ) O(\log n) O(logn) 。排序需要 O ( log n ) O(\log n) O(logn) 的递归栈空间。 解法2 快速选择
根据方法一的推导 x x x 取数组 nums \textit{nums} nums 第 ⌊ n 2 ⌋ \lfloor \frac{n}{2} \rfloor ⌊2n⌋ 小元素从 0 0 0 开始计数时所需要的移动数最少。求解数组第 k k k 小元素可以使用快速选择算法。
class Solution {
public:int quickSelect(vectorint nums, int left, int right, int index) {int q randomPartition(nums, left, right);if (q index) {return nums[q];} else {return q index ? quickSelect(nums, q 1, right, index) : quickSelect(nums, left, q - 1, index);}}inline int randomPartition(vectorint nums, int left, int right) {int i rand() % (right - left 1) left;swap(nums[i], nums[right]);return partition(nums, left, right);}inline int partition(vectorint nums, int left, int right) {int x nums[right], i left - 1;for (int j left; j right; j) {if (nums[j] x) {swap(nums[i], nums[j]);}}swap(nums[i 1], nums[right]);return i 1;}int minMoves2(vectorint nums) {srand(time(0));int n nums.size(), x quickSelect(nums, 0, n - 1, n / 2), ret 0;for (int i 0; i n; i) {ret abs(nums[i] - x);}return ret;}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n) 其中 n n n 是数组 nums \textit{nums} nums 的长度。快速选择算法的平均时间复杂度为 O ( n ) O(n) O(n) 。空间复杂度 O ( log n ) O(\log n) O(logn) 。递归栈的平均占用空间为 O ( log n ) O(\log n) O(logn) 。
