Java&C++题解与拓展——leetcode462.最少移动次数【快速选择、nth

• 题目要求
• • 理解
• 思路：数学（中位数）
• • Java
  • C++
• 思路：快速选择
• • Java
  • C++
  • • STL nth_element()
• 总结

找中位数，属于TopK问题。

• 很容易想到，都变成中间的数就好了。
  • 证明过程懒得写，请看三叶姐姐
• 所以把数组排个序，找中位数，计算每个数和中位数的距离之和即可。

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

• 时间复杂度： O ( n log ⁡ n ) O(nlog n) O(nlogn)
• 空间复杂度： O ( log ⁡ n ) O(log n) O(logn)

class Solution {
public:
    int minMoves2(vector& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), mid = nums[(n - 1) / 2], res = 0;
        for(int i : nums)
            res += abs(mid - i);
        return res;
    }
};

• 时间复杂度： O ( n log ⁡ n ) O(nlog n) O(nlogn)
• 空间复杂度： O ( log ⁡ n ) O(log n) O(logn)

• 和刚才的思路一样，不过排序算法换成快排，基于快排找数组中第 ⌊ n 2 ⌋ lfloor frac{n}{2}rfloor ⌊2n​⌋小的元素。

【注意快排移动指针时的加一和减一】

class Solution {
    Random ran = new Random(); // 用于随机拆分
    int[] nums;

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

    // 快速选择[f,l]范围内第target大的数
    public int quickSelect(int first, int last, int target) {
        int q = randomPartition(first, last);
        if(q == target)
            return nums[q];
        else
            return q < target ? quickSelect(q + 1, last, target) : quickSelect(first, q - 1, target); //注意左右区间
    }
    public int randomPartition(int first, int last) {
        int i = ran.nextInt(last - first + 1) + first;
        swap(i, last);
        return partition(first, last);
    }
    public int partition(int first, int last) {
        int x = nums[last], i = first - 1;
        for(int j = first; j < last; ++j) {
            if(nums[j] <= x) {
                ++i;
                swap(i, j);
            }
        }
        swap(i + 1, last);
        return i + 1;
    }
    public void swap(int a, int b) {
        int t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }
}

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( log ⁡ n ) O(log n) O(logn)

C++有一个类似快排思路的内置函数

class Solution {
public:
    int minMoves2(vector& nums) {
        int mid = nums.size() / 2;
        nth_element(nums.begin(), nums.begin() + mid, nums.end());
        int res = 0;
        for(int i : nums)
            res += abs(i - nums[mid]);
        return res;
    }
};

• 时间复杂度： O ( n ) O(n) O(n)
• 空间复杂度： O ( 1 ) O(1) O(1)

• 学习参考链接
• nth_element(first, n, last, comp)
  • 找数组/容器在 f i r s t first first到 l a s t last last范围内第 n n n大的数，也可以改为降序找第 n n n小的数；
  • c o m p comp comp为自定义排序规则，可选。

本来以为是个简单的数学推导，找中位数的简单题。可以引申到TopK问题，使用快排解决，get新函数nth_element。

【莫名开心的一天】