462. Minimum Moves to Equal Array Elements II

Leetcode 問題: 462. Minimum Moves to Equal Array Elements II
Categories:
Tags:

題目

Given an integer array nums of size n, return the minimum number of moves required to make all array elements equal.

In one move, you can increment or decrement an element of the array by 1.

Test cases are designed so that the answer will fit in a 32-bit integer.

傳入一個數字陣列 nums，陣列大小是 n，回傳最少需要加減多少數字，可以讓整個陣列的數值都相同

  • 移動一步等於是加減 1
  • 答案為 32-bit 整數

Example

Input: nums = [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]

Input: nums = [1,10,2,9]
Output: 16

演算法 1 : 計算與中位數差

1. 排序陣列

先將傳入整數陣列排序，以便取得中位數位置的數字

2. 選擇中位數

取得數字陣列中位數，所有數字與中位數的差，就是要移動的數字

3. 計算每個數字與中為數字差的總數

將所有要移動的數字加總，就可以求得總共要敵動的步數是多少了

演算法 1 答案

JavaScript

function minMoves2(numsList) {
    // 依照數字小到大排序
    numsList.sort(function (a, b) {
        return a - b;
    });
    // 總元素數量
    var totalElements = numsList.length;
    // 中位數元素位置
    var mediumIndex = Math.floor(totalElements / 2);
    // 中位數
    var mediumNumber = numsList[mediumIndex];
    var totalMove = 0;
    for (var i = 0; i < numsList.length; i++) {
        // 目前數字
        var currentNumber = numsList[i];
        // 目前數字與中位數數字差
        var currentNumberDiffWithMediumNumber = Math.abs(currentNumber - mediumNumber);
        // 加總移動數字
        totalMove += currentNumberDiffWithMediumNumber;
    }
    return totalMove;
}

TypeScript

function minMoves2(numsList: number[]): number {
    // 依照數字小到大排序
    numsList.sort(function(a, b) {
        return a - b;
    });

    // 總元素數量
    let totalElements = numsList.length;
    // 中位數元素位置
    let mediumIndex = Math.floor(totalElements / 2);
    // 中位數
    let mediumNumber = numsList[mediumIndex];

    let totalMove = 0;
    for (let i = 0; i < numsList.length; i++) {
        // 目前數字
        let currentNumber = numsList[i];
        // 目前數字與中位數數字差
        let currentNumberDiffWithMediumNumber = Math.abs(currentNumber - mediumNumber);
        // 加總移動數字
        totalMove += currentNumberDiffWithMediumNumber;
    }

    return totalMove;
};

演算法 2 : 計算最大最小值差

1. 排序陣列

先將傳入整數陣列排序，以便計算與中位數位置的差

2. 計算左右指標差

因為要計算所有數字與中位數的差

中位數與左指標的差，加上中位數與右指標的差，這個差的總和相當於右指標與左指標的差

所以就直接將右指標與左指標的差加總，再移動左右指標，直到左右指標交叉即可

演算法 2 答案

TypeScript

function minMoves2(numsList: number[]): number {
    // 依照數字小到大排序
    numsList.sort(function(a, b) {
        return a - b;
    });

    // 設定指標
    let leftPointer = 0;
    let rightPointer = numsList.length - 1;

    let totalMove = 0;
    while (leftPointer <= rightPointer) {
        // 當左右指標尚未交叉，繼續運算
        totalMove += numsList[rightPointer] - numsList[leftPointer];
        leftPointer++;
        rightPointer--;
    }

    return totalMove;
};

演算法 3 : 使用 partition 取得中位數數字

演算法 3 答案

TypeScript

function minMoves2(numsList: number[]): number {
    // 中位數數字位置
    let mediumNumberIndex: number = Math.floor(numsList.length / 2);
    let mediumNumber: number = findKthSmallestNumber(numsList, mediumNumberIndex);
    let totalMove = 0;
    for (let i = 0; i < numsList.length; i++) {
        let currentNumber = numsList[i];
        let diffNumber = Math.abs(currentNumber - mediumNumber);
        totalMove += diffNumber
    }

    return totalMove;
};

function findKthSmallestNumber(numsList: number[], kth: number): any {
    // 設定指標
    let leftPointer = 0;
    let rightPointer = numsList.length - 1;

    while (leftPointer < rightPointer) {
        // 切割點
        let partitionPointer = partitionNumberList(numsList, leftPointer, rightPointer);

        if (partitionPointer == kth) {
            // 如果「切割點」剛好是第 k 個數字，不需要再找了，直接回傳切割點指標數字
            break;
        }

        if (partitionPointer < kth) {
            // 如果「切割點」比第 k 個數字還要小，表示目前切割點是偏左，在 k 的左邊
            // 所以左邊的數字一定是比較小不用找，可能的答案在右邊
            // 往右方部分找，找下一個切割點
            leftPointer = partitionPointer + 1;
        } else {
            // 如果「切割點」比第 k 個數字還要大，表示目前切割點是偏右，在 k 的右邊
            // 所以右邊的數字一定是比較大不用找，可能的答案在左邊
            // 往左方部分找，找下一個切割點
            rightPointer = partitionPointer - 1;
        }
    }

    return numsList[kth];
}


// 切割數字陣列
var partitionNumberList = function(numsList: number[], leftPointer: number, rightPointer: number): number {
    // 選擇右指標當作「檢查數字」
    let pivotCheckNumber = numsList[rightPointer];
    // 較小數字紀錄指標設定為左指標
    let smallerNumberPointer = leftPointer;

    for(let i = leftPointer; i < rightPointer; i++) {
        // 從「左指標」檢查到「右指標」
        if (numsList[i] <= pivotCheckNumber) {
            // 若「目前檢查的數字」小於等於「檢查的數字」
            // 將目前數字放到「較小數字記錄指標」位置
            [numsList[smallerNumberPointer], numsList[i]] = [numsList[i], numsList[smallerNumberPointer]];
            // 「較小數字記錄指標」位置往後移動
            smallerNumberPointer++;
        }
    }
    // 檢查完成，確認「較小數字記錄指標」數字都比「檢查數字」小
    // 「較小數字記錄指標」與「檢查數字」交換
    //  - 「較小數字記錄指標」左方都是比「檢查數字」小的數字
    //  - 「較小數字記錄指標」右方都是比「檢查數字」大的數字
    [numsList[smallerNumberPointer], numsList[rightPointer]] = [numsList[rightPointer], numsList[smallerNumberPointer]];

    return smallerNumberPointer;
};

參考資料