摘要:如果是偶數的話,中位數是兩個中間的數之間的任意一個數字。將從最小值逐步向最大值移動。也就是說,如果在和間移動,二者到的距離和是不變的。同理,當到達中位數,并且繼續向右移動時,會發現整體數組的移動距離也隨之增加。
題目要求
Given a non-empty integer array, find the minimum number of moves required to make all array elements equal, where a move is incrementing a selected element by 1 or decrementing a selected element by 1. You may assume the array"s length is at most 10,000. Example: Input: [1,2,3] Output: 2 Explanation: Only two moves are needed (remember each move increments or decrements one element): [1,2,3] => [2,2,3] => [2,2,2]
問最少需要多少次操作,能夠將數組中所有元素的值修改為一樣的(操作是指將數組中的元素加一或者減一)
思路和代碼其實這題就是找到數組的中位數,該中位數就是最終修改成的元素。當然了,這里的中位數不是廣義上的中位數,當數組的元素為奇數時,“中位數”是從小到大排列后位于中間的數。如果是偶數的話,“中位數”是兩個中間的數之間的任意一個數字。
這里很多人會以為是計算出平均值作為最終元素,其實不然。簡單的講一下為何“中位數”是最終元素的原因。假設有一個長度為n的數組,其中包括元素a1, a2, ... an,已知該數組已經有序,則可以知道,對于任意一個數字M,它到各個元素的距離和dist為|a[1] - M| + |a[2] - M| + ... + |a[n] - M|。如果M
現在開始找M的最佳位置。將M從最小值a1逐步向最大值an移動。假設M=a1+1且M 代碼如下: public int minMoves2(int[] nums) {
Arrays.sort(nums);
int i = 0, j = nums.length - 1, result = 0;
while(i < j) {
result += nums[j--] - nums[i++];
}
return result;
}
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/75666.html
摘要:對二者進行計算可以得出。假如并不是每一步都會將最小的值加一,則這個值永遠是最小值,它將永遠無法達到最終的目標值。 題目要求 Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move ...
摘要:在線網站地址我的微信公眾號完整題目列表從年月日起,每天更新一題,順序從易到難,目前已更新個題。這是項目地址歡迎一起交流學習。 這篇文章記錄我練習的 LeetCode 題目,語言 JavaScript。 在線網站:https://cattle.w3fun.com GitHub 地址:https://github.com/swpuLeo/ca...我的微信公眾號: showImg(htt...
摘要:月下半旬攻略道題,目前已攻略題。目前簡單難度攻略已經到題,所以后面會調整自己,在刷算法與數據結構的同時,攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題,目前已攻略 100 題。 一 目錄 不折騰的前端,和咸魚有什么區別...
摘要:題目要求假設一個二維的整數數組中每一行表示一個區間,每一行的第一個值表示區間的左邊界,第二個值表示區間的右邊界。 題目要求 Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal ...
摘要:這樣,我們可以保證隊列里的元素是從頭到尾降序的,由于隊列里只有窗口內的數,所以他們其實就是窗口內第一大,第二大,第三大的數。 Sliding Window Maximum Given an array nums, there is a sliding window of size k which is moving from the very left of the array to...
閱讀 2570·2021-09-06 15:02
閱讀 3200·2021-09-02 10:18
閱讀 2822·2019-08-30 15:44
閱讀 685·2019-08-30 15:43
閱讀 1948·2019-08-30 14:08
閱讀 2758·2019-08-30 13:16
閱讀 1397·2019-08-26 13:52
閱讀 931·2019-08-26 12:21