LeetCode Minimum Moves to Equal Array Elements II Given a non-empty integer array, find the minimum number of moves required to make all array elements equal, where a move is incrementing a selected element by 1 or decrementing a selected element by 1. You may assume the array’s length is at most 10,000. Example:

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

---

是LeetCode Minimum Moves to Equal Array Elements的改编题。这次每次只能改变一个数，让其增大1或者减小1，问最小需要多少次操作能使所有数字相等。 其实看样例就能猜到，最终统一的那个数是原数组中的中位数。这就好办了，对原数组排个序，然后累加所有元素和中位数的绝对值就可以了。 代码如下： [cpp] class Solution { public: int minMoves2(vector<int>& nums) { sort(nums.begin(), nums.end()); int ans = 0, mid = nums[nums.size() / 2]; for (const int& i : nums)ans += abs(i – mid); return ans; } }; [/cpp] 本代码提交AC，用时22MS。 排好序之后还有另一种方法求操作数，比如排好序是1,3,5,7,9，最终所有数都要变成5。之前的做法是所有数和5作差求绝对值加和，现在可以这样做，1到5需要(5-1)次操作，9变成5需要(9-5)次操作，累加就是(5-1)+(9-5)=(9-1)，所以我们取排序之后的首位元素，互相作差即可。这就看起来和中位数没关系了。 代码如下： [cpp] class Solution { public: int minMoves2(vector<int>& nums) { sort(nums.begin(), nums.end()); int ans = 0, i = 0, j = nums.size() – 1; while (i < j) { ans += nums[j–] – nums[i++]; } return ans; } }; [/cpp] 本代码提交AC，用时19MS。 既然是要求中位数，其实不用对数组排序都可以做到，就是之前的求第k大数LeetCode Kth Largest Element in an Array，直接借用那个函数即可。STL也有类似的函数nth_element。 [cpp] class Solution { private: int helper(vector<int>& nums, int left, int right, int k) { if (left == right)return nums[left]; int pivot = nums[left]; int l = left, r = right; while (l < r) { while (l < r&&nums[r] <= pivot)–r; if (l >= r)break; nums[l] = nums[r]; while (l < r&&nums[l] >= pivot)++l; if (l >= r)break; nums[r] = nums[l]; } nums[l] = pivot; if (l + 1 == k)return pivot; if (k < l + 1)return helper(nums, left, l – 1, k); else return helper(nums, l + 1, right, k); } public: int minMoves2(vector<int>& nums) { //int ans = 0, mid = helper(nums, 0, nums.size() – 1, nums.size() / 2 + 1); nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end()); int ans = 0, mid = nums[nums.size() / 2]; for (const int& i : nums)ans += abs(i – mid); return ans; } }; [/cpp] 本代码提交AC，用时13MS。]]>

LeetCode Minimum Moves to Equal Array Elements Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n – 1 elements by 1. Example:

Input:
[1,2,3]
Output:
3
Explanation:
Only three moves are needed (remember each move increments two elements):
[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

---

给定一个长度为n数组，每次操作是把其中n-1个数加1，问需要多少次操作才能使数组中的所有元素都相等。 很有意思的数学题。常规思路是，每次找出数组中的最大数，然后对剩下的n-1个数加1，如此循环直到所有元素相等。但是这种解法每次操作都需要O(n)的复杂度，肯定会TLE。 另一个思路，对除最大数之外的所有数加1，相当于其他数不变，把最大数减1。所以可以先找到数组中的最小数，然后累加数组中各元素与最小值之差即可。 代码如下： [cpp] class Solution { public: int minMoves(vector<int>& nums) { int m = INT_MAX, ans = 0; for (const int& i : nums)m = min(m, i); for (const int& i : nums)ans += i – m; return ans; } }; [/cpp] 本代码提交AC，用时56MS。]]>

215. Kth Largest Element in an Array215. Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.215. Kth Largest Element in an Array

---

本题要求一个未排序数组中第k大的数。
解法1，直接从大到小排序，然后取第k个数，时间复杂度O(nlgn)。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k)
    {
        sort(nums.begin(), nums.end(), std::greater<int>());
        return nums[k – 1];
    }
};

本代码提交AC，用时16MS。
解法2，借助快排的思路，每次选择一个枢纽pivot，把区间[left,right]划分为比pivot大和小的两个部分，然后就能确定pivot的最终位置，如果其下标正好是k-1，则说明pivot就是第k大的数。否则可以判断第k大的数在左半边还是右半边，然后递归在其中一半查找第k大的数。时间复杂度可以由T(n)=T(n/2)+O(n)解出是O(n)，注意我们只需要在其中一半递归，所以是加一个T(n/2)。
代码如下：

class Solution {
private:
    int helper(vector<int>& nums, int left, int right, int k)
    {
        if (left == right)
            return nums[left];
        int pivot = nums[left];
        int l = left, r = right;
        while (l < r) {
            while (l < r && nums[r] <= pivot)
                –r;
            if (l >= r)
                break;
            nums[l] = nums[r];
            while (l < r && nums[l] >= pivot)
                ++l;
            if (l >= r)
                break;
            nums[r] = nums[l];
        }
        nums[l] = pivot;
        if (l + 1 == k)
            return pivot;
        if (k < l + 1)
            return helper(nums, left, l – 1, k);
        else
            return helper(nums, l + 1, right, k);
    }
public:
    int findKthLargest(vector<int>& nums, int k) { return helper(nums, 0, nums.size() – 1, k); }
};

本代码提交AC，用时39MS，居然比直接排序还慢。。。
解法3，使用堆排序。对原数组建一个最大堆，然后不断的把前k-1个堆顶弹出，下一个堆顶元素就是第k大的元素。建堆时间为O(n)，维护堆的性质需要O(lgn)时间，所以总时间复杂度为O(klgn+n)。
代码如下：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k)
    {
        priority_queue<int> pq(nums.begin(), nums.end());
        for (int i = 0; i < k – 1; ++i)
            pq.pop();
        return pq.top();
    }
};

本代码提交AC，用时9MS，是最快的。
二刷。还是使用快排划分的方法，但是这次把partition的过程单独抽出来了，逻辑更清晰，代码如下：

class Solution {
private:
    int partition(vector<int>& nums, int start, int end)
    {
        if (start >= end)
            return start;
        int i = start, j = end, pivot = nums[start];
        while (i < j) {
            while (i < j && nums[j] <= pivot)
                –j; // 注意符号，从大到小排序
            if (i < j) {
                nums[i] = nums[j];
                ++i;
            }
            while (i < j && nums[i] > pivot)
                ++i; // 注意符号，从大到小排序
            if (i < j) {
                nums[j] = nums[i];
                –j;
            }
        }
        nums[i] = pivot;
        return i;
    }
public:
    int findKthLargest(vector<int>& nums, int k)
    {
        int start = 0, end = nums.size() – 1;
        while (true) {
            int p = partition(nums, start, end);
            if (p + 1 == k)
                return nums[p];
            else if (p + 1 < k)
                start = p + 1;
            else
                end = p – 1;
        }
        return -1;
    }
};

本代码提交AC，用时23MS。

三刷。更简洁不易出错的快排划分方法：

class Solution {
private:
	int FindK(vector<int>& nums, int left, int right, int k) {
		int pivot = nums[right];
		int next_idx = left;
		for (int i = left; i <= right; ++i) {
			if (nums[i] > pivot) {
				swap(nums[i], nums[next_idx++]);
			}
		}
		swap(nums[right], nums[next_idx]);
		int rank = next_idx + 1 - left;
		if (rank == k)return pivot;
		else if (k < rank)return FindK(nums, left, next_idx - 1, k);
		else return FindK(nums, next_idx + 1, right, k - rank);
	}
public:
	int findKthLargest(vector<int>& nums, int k) {
		return FindK(nums, 0, nums.size() - 1, k);
	}
};

本代码提交AC，用时212MS。

201. Bitwise AND of Numbers Range

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

Example 1:

Input: [5,7]
Output: 4

Example 2:

Input: [0,1]
Output: 0

---

求把从m~n的所有整数相与的结果。
暴力方法就是从m到n遍历一遍，把所有数都相与一下。但是TLE。
这题明显是个数学题或者找规律题。网上的解法大多数是这样的，把m~n的所有数相与的结果等于m和n这两个数的二进制的最长公共前缀。比如题目中的[5,7]，5和7的二进制分别为101和111，最长公共前缀就是100=4，后两位不一样也要补0。再比如[26,30]，26和30的二进制分别为11010和11110，最长公共前缀为11000=24。
知道这个规律就好办了，因为m和n都是正数，不断同时把m和n往右移，直到他们相等，最后再把m往左移回去就是最终结果。代码如下：

class Solution {
public:
    int rangeBitwiseAnd(int m, int n)
    {
        int offset = 0;
        while (m != n) {
            m >>= 1;
            n >>= 1;
            ++offset;
        }
        return m << offset;
    }
};

本代码提交AC，用时69MS。

二刷。看下面的图，m和n最长公共前缀后面的二进制位，在[m,n]范围内都在不停的变化，也就是有0也有1，所以全与之后肯定都是0，只有公共前缀的1相与不会变0，所以要找公共前缀。

179. Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

Example 1:

Input: [10,2]
Output: "210"

Example 2:

Input: [3,30,34,5,9]
Output: "9534330"

Note: The result may be very large, so you need to return a string instead of an integer.

---

给定一个数组，要把数组中所有的数拼成一个长的数，问能够拼成的最大的数是多少，要求返回这个最大数的字符串形式。

要想长数越大，则数组中“越大的数”应该排在前面，这里的“大”是指字典序，比如9就比34大，所以9应该在字符串中排前面。所以大的思路是先把数字数组转换为对应的字符串数组，然后按字典序对字符串数组排序，最后按先后顺序拼接起来。

还有一个问题是，遇到30和34时，应该把34排在30的前面，即3430>3034，这符合字典序，没什么问题。

另一个问题是，遇到一个数是另一个数的前缀的情况，应该怎么排序呢，比如34和349时，应该是349排在34的前面，因为34934>34349，这也符合字典序。但是，如果是34和341，正确的排序应该是34排在341的前面，因为34341>34134，此时就不符合字典的降序了。所以需要自定义一个对字符串的排序算法，此算法要对字符串s1和s2进行比较，方法是判断s1+s2和s2+s1的字典序，因为这就是这两个字符串按不同顺序拼接之后的大小。

最后一个问题，如果遇到数组是[0,0]，即两个0时，能拼成的最大数是0，但是如果先转换成字符数组之后，拼成的数就是00了。所以在最后，我们判断一下开头的字符是否为’0’，如果是，说明这个数就是0了，不管后面是否还有多余的字符’0’，我们都只返回”0″。如果开头的字符不是’0’，则多个’0’是有效的，比如30和300是不同的两个数。

完整代码如下：

bool comp(const string& s1, const string& s2)
{
    string tmp1 = s1 + s2, tmp2 = s2 + s1;
    return tmp1 > tmp2;
}
class Solution {
public:
    string largestNumber(vector<int>& nums)
    {
        vector<string> snums;
        for (size_t i = 0; i < nums.size(); ++i)
            snums.push_back(to_string(nums[i]));
        sort(snums.begin(), snums.end(), comp);
        string ans = "";
        for (size_t i = 0; i < snums.size(); ++i)
            ans += snums[i];
        if (!ans.empty() && ans[0] == ‘0’)
            return "0";
        return ans;
    }
};

本代码提交AC，用时6MS。

代码中注意一点，自定义的比较函数不能是类的成员函数，要不然会报错“非标准语法；请使用 “&” 来创建指向成员的指针”，这个错误提示很奇怪。后来才知道比较函数必须定义成全局函数或者静态函数，因为sort自己就是全局或静态函数，无法调用成员函数。