python3 解法, 执行用时: 4044 ms, 内存消耗: 20.4 MB, 提交时间: 2022-11-29 12:20:20

class Helper:
    @staticmethod
    def partition(nums: List[int], l: int, r: int) -> int:
        pivot = nums[r]
        i = l - 1
        for j in range(l, r):
            if nums[j] <= pivot:
                i += 1
                nums[i], nums[j] = nums[j], nums[i]
        nums[i + 1], nums[r] = nums[r], nums[i + 1]
        return i + 1

    @staticmethod
    def randomPartition(nums: List[int], l: int, r: int) -> int:
        i = randint(l, r)
        nums[r], nums[i] = nums[i], nums[r]
        return Helper.partition(nums, l, r)

    @staticmethod
    def quickSelected(nums: List[int], l: int, r: int, k: int) -> int:
        index = Helper.randomPartition(nums, l, r)
        if k == index:
            return nums[k]
        if k < index:
            return Helper.quickSelected(nums, l, index - 1, k)
        return Helper.quickSelected(nums, index + 1, r, k)

class Solution:
    def minMoves2(self, nums: List[int]) -> int:
        seed(time())
        x = Helper.quickSelected(nums, 0, len(nums) - 1, len(nums) // 2)
        return sum(abs(num - x) for num in nums)

golang 解法, 执行用时: 72 ms, 内存消耗: 5.4 MB, 提交时间: 2022-11-29 12:20:00

func partition(a []int, l, r int) int {
    x := a[r]
    i := l - 1
    for j := l; j < r; j++ {
        if a[j] <= x {
            i++
            a[i], a[j] = a[j], a[i]
        }
    }
    a[i+1], a[r] = a[r], a[i+1]
    return i + 1
}

func randomPartition(a []int, l, r int) int {
    i := rand.Intn(r-l+1) + l
    a[i], a[r] = a[r], a[i]
    return partition(a, l, r)
}

func quickSelect(a []int, l, r, index int) int {
    q := randomPartition(a, l, r)
    if q == index {
        return a[q]
    }
    if q < index {
        return quickSelect(a, q+1, r, index)
    }
    return quickSelect(a, l, q-1, index)
}

func minMoves2(nums []int) (ans int) {
    rand.Seed(time.Now().UnixNano())
    x := quickSelect(nums, 0, len(nums)-1, len(nums)/2)
    for _, num := range nums {
        ans += abs(num - x)
    }
    return
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

javascript 解法, 执行用时: 128 ms, 内存消耗: 42.4 MB, 提交时间: 2022-11-29 12:19:39

/**
 * @param {number[]} nums
 * @return {number}
 */
var minMoves2 = function(nums) {
    let n = nums.length, x = quickSelect(nums, 0, n - 1, Math.floor(n / 2)), ret = 0;
    for (let i = 0; i < n; ++i) {
        ret += Math.abs(nums[i] - x);
    }
    return ret;
}

const quickSelect = (nums, left, right, index) => {
    const 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);
    }
}

const randomPartition = (nums, left, right) => {
    const i = Math.floor(Math.random() * (right - left + 1)) + left;
    swap(nums, i, right);
    return partition(nums, left, right);
}

const partition = (nums, left, right) => {
    let x = nums[right], i = left - 1;
    for (let j = left; j < right; ++j) {
        if (nums[j] <= x) {
            ++i;
            swap(nums, i, j);
        }
    }
    swap(nums, i + 1, right);
    return i + 1;
}

const swap = (nums, index1, index2) => {
    const temp = nums[index1];
    nums[index1] = nums[index2];
    nums[index2] = temp;
}

java 解法, 执行用时: 44 ms, 内存消耗: 42.4 MB, 提交时间: 2022-11-29 12:19:08

class Solution {
    Random random = new Random();

    public int minMoves2(int[] nums) {
        int n = nums.length, x = quickSelect(nums, 0, n - 1, n / 2), ret = 0;
        for (int i = 0; i < n; ++i) {
            ret += Math.abs(nums[i] - x);
        }
        return ret;
    }

    public int quickSelect(int[] 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);
        }
    }

    public int randomPartition(int[] nums, int left, int right) {
        int i = random.nextInt(right - left + 1) + left;
        swap(nums, i, right);
        return partition(nums, left, right);
    }

    public int partition(int[] nums, int left, int right) {
        int x = nums[right], i = left - 1;
        for (int j = left; j < right; ++j) {
            if (nums[j] <= x) {
                ++i;
                swap(nums, i, j);
            }
        }
        swap(nums, i + 1, right);
        return i + 1;
    }

    public void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

java 解法, 执行用时: 4 ms, 内存消耗: 42.1 MB, 提交时间: 2022-11-29 12:18:35

class Solution {
    public int minMoves2(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length, ret = 0, x = nums[n / 2];
        for (int i = 0; i < n; i++) {
            ret += Math.abs(nums[i] - x);
        }
        return ret;
    }
}

javascript 解法, 执行用时: 64 ms, 内存消耗: 43.1 MB, 提交时间: 2022-11-29 12:18:17

/**
 * @param {number[]} nums
 * @return {number}
 */
var minMoves2 = function(nums) {
    nums.sort((a, b) => a - b);
    let n = nums.length, ret = 0, x = nums[Math.floor(n / 2)];
    for (let i = 0; i < n; i++) {
        ret += Math.abs(nums[i] - x);
    }
    return ret;
};

golang 解法, 执行用时: 12 ms, 内存消耗: 4.4 MB, 提交时间: 2022-11-29 12:18:01

func minMoves2(nums []int) (ans int) {
    sort.Ints(nums)
    x := nums[len(nums)/2]
    for _, num := range nums {
        ans += abs(num - x)
    }
    return
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

python3 解法, 执行用时: 44 ms, 内存消耗: 15.9 MB, 提交时间: 2022-11-29 12:17:46

class Solution:
    def minMoves2(self, nums: List[int]) -> int:
        nums.sort()
        return sum(abs(num - nums[len(nums) // 2]) for num in nums)