22/05/18：乘法表中第k小的数

给定高度m 、宽度n 的一张 m * n的乘法表，以及正整数k，你需要返回表中第k 小的数字。

例 1：

输入: m = 3, n = 3, k = 5输出: 3解释: 乘法表:123246369第5小的数字是 3 (1, 2, 2, 3, 3).

思路：二分查找

• 考虑每一行中不超过x的个数有几个：min(|x/i|, n)个，因此乘法表总共不超过x的个数即为每一行中的不超过x的个数之和。
• 对于下列代码中为什么返回的left一定在乘法表中？
  • 首先，乘法表中第k小的数字一定在[left, right]中，即在集合{left, left+1, ..., x, ...right}中。
  • 因为[left, right]最后会收敛于某个点，而由于乘法表中第k小数字一定在[left, right]中，所以该点必是x。
  • 在循环迭代的过程中，left不一定在乘法表中，但是x一定在[left, right]中。循环跳出的条件是left=right， 因此有left=right=x

class Solution {    public int findKthNumber(int m, int n, int k) {        int left = 1, right = m * n;        while (left < right) {            int mid = left + (right - left) / 2;            int temp = 0;            for (int i = 1; i <= m; i++) {                temp += Math.min(mid / i, n);            }            if (temp >= k) {                right = mid;            } else {                left = mid + 1;            }        }        return left;    }}

# 22/05/19：最少移动次数使数组元素相等 II

给你一个长度为 n 的整数数组 nums ，返回使所有数组元素相等需要的最少移动数。在一步操作中，你可以使数组中的一个元素加 1 或者减 1 。

示例 1：

输入：nums = [1,2,3]输出：2解释：只需要两步操作（每步操作指南使一个元素加 1 或减 1）：[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

思路：实际上找到排序数组后的中位数即可。

class Solution {    public int minMoves2(int[] nums) {        Arrays.sort(nums);        int left = 0, right = nums.length - 1;        int mid = left + (right - left) / 2;        int res = 0;        for (; left <= right; left++, right--) {            res += nums[right] - nums[left];        }        return res;    }}