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;
};

参考资料