IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> LeetCode 每日一题——462. 最少移动次数使数组元素相等 II -> 正文阅读

[数据结构与算法]LeetCode 每日一题——462. 最少移动次数使数组元素相等 II

1.题目描述

462. 最少移动次数使数组元素相等 II

给你一个长度为 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

2.思路

2.1 代码

题目要求找到每一位数字移动的最小次数,因此考虑先对数组进行排序,然后取中位数,再对每一位依次和中位数进行对比即可。这个时候便会遇到数组个数是奇数和偶数两种情况:

  • 数组个数是奇数的话直接取最中间元素即可,即 mid = nums.length / 2 ;
  • 数组个数是偶数的话中位数有两个,即最中间两位,这个时候取这两个任意一位均可,证明如下:

假设数组 n u m s = a 0 , a 1 , a 2 . . . a m i d ? 1 , a m i d . . . a n ? 2 , a n ? 1 nums={a_0,a_1,a_2...a_{mid-1},a_{mid}...a_{n-2},a_{n-1}} nums=a0?,a1?,a2?...amid?1?,amid?...an?2?,an?1? 。其中 n 为偶数, a m i d ? 1 a_{mid-1} amid?1? a m i d a_{mid} amid? 为该有序数组的两个中位数。
如果选择 a m i d ? 1 a_{mid-1} amid?1? 进行操作,在角标 mid-1 之前的都是比 a m i d ? 1 a_{mid-1} amid?1?小的,之后都是比 a m i d ? 1 a_{mid-1} amid?1?大的,因此得到移动次数:
t i m e s = ( a m i d ? 1 ? a 1 ) + ( a m i d ? 1 ? a 2 ) + . . . + ( a m i d ? 1 ? a m i d ? 1 ) + ( a m i d ? a m i d ? 1 ) + . . . + ( a n ? 2 ? a m i d ? 1 ) + ( a n ? 1 ? a m i d ? 1 ) = ( ? a 1 ) + ( ? a 2 ) + . . . + ( ? a m i d ? 1 ) + a m i d + . . . + a n ? 2 + a n ? 1 \begin{aligned} times&=(a_{mid-1}-a_1)+(a_{mid-1}-a_2)+...+(a_{mid-1}-a_{mid-1})+(a_{mid}-a_{mid-1})+...+(a_{n-2}-a_{mid-1})+(a_{n-1}-a_{mid-1})\\ &=(-a_1)+(-a_2)+...+(-a_{mid-1})+a_{mid}+...+a_{n-2}+a_{n-1} \end{aligned} times?=(amid?1??a1?)+(amid?1??a2?)+...+(amid?1??amid?1?)+(amid??amid?1?)+...+(an?2??amid?1?)+(an?1??amid?1?)=(?a1?)+(?a2?)+...+(?amid?1?)+amid?+...+an?2?+an?1??
同理可得选用 a m i d + 1 a_{mid+1} amid+1? 进行操作的结果:
t i m e s 2 = ( a m i d ? a 1 ) + ( a m i d ? a 2 ) + . . . + ( a m i d ? a m i d ? 1 ) + ( a m i d ? a m i d ) + . . . + ( a n ? 2 ? a m i d ) + ( a n ? 1 ? a m i d ) = ( ? a 1 ) + ( ? a 2 ) + . . . + ( ? a m i d ? 1 ) + a m i d + . . . + a n ? 2 + a n ? 1 \begin{aligned} times_2&=(a_{mid}-a_1)+(a_{mid}-a_2)+...+(a_{mid}-a_{mid-1})+(a_{mid}-a_{mid})+...+(a_{n-2}-a_{mid})+(a_{n-1}-a_{mid})\\ &=(-a_1)+(-a_2)+...+(-a_{mid-1})+a_{mid}+...+a_{n-2}+a_{n-1} \end{aligned} times2??=(amid??a1?)+(amid??a2?)+...+(amid??amid?1?)+(amid??amid?)+...+(an?2??amid?)+(an?1??amid?)=(?a1?)+(?a2?)+...+(?amid?1?)+amid?+...+an?2?+an?1??
从上面结果可以看出 t i m e s times times t i m e s 2 times_2 times2? 相等。
代码如下:

class Solution {
    public int minMoves2(int[] nums) {
        if (nums.length == 2) {
            return Math.abs(nums[0] - nums[1]);
        }
        Arrays.sort(nums);
        int mid = nums.length / 2;
        long ans1 = 0L;
        for (int num : nums) {
            ans1 += Math.abs(num - nums[mid]);
        }
        return (int) ans1;
    }
}

2.2 测试结果

通过测试
测试结果

3.总结

  • 先对数组进行排序,然后选择中位数进行移动操作
  • 数组长度为奇数时,选择最中间的元素;数组长度为偶数时,中间两个选择任意一个都正确
  数据结构与算法 最新文章
《算法系列》之 数组
Python描述 LeetCode 剑指 Offer II 091. 粉
【八大排序①】插入排序(直接插入排序、希
【恋上数据结构与算法】理论 三: 链表:Li
LeetCode 剑指 Offer II 091.粉刷房子 - 原
2022-06-27 数据结构与算法-递归、冒泡、插
AcWing 848. 有向图的拓扑序列(拓扑排序模
排序算法-C++
C语言求最大公约数
2021.12.09 - SX09-08.跳跃游戏 II
上一篇文章      下一篇文章      查看所有文章
加:2022-05-21 19:13:41  更:2022-05-21 19:16:13 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
360图书馆 购物 三丰科技 阅读网 日历 万年历 2022年6日历 -2022/6/30 16:03:34-
图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码