21 调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
示例：
输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。提示：
0 <= nums.length <= 500000 <= nums[i] <= 10000
题解
class Solution {
public:
vector<int> exchange(vector<int>& nums) {
int i=0,j=nums.size()-1;
while(i<j){
//i为奇数
if(nums[i]%2==1)
{
i++;continue;
}
//j为偶数
if(nums[j]%2==0)
{
j--;continue;
}
//j为奇数，该情况下i必为偶数
if(nums[j]%2==1)
{
swap(nums[i],nums[j]);
j--;
i++;
continue;
}
}
return nums;
}
};
//更简洁的写法
class Solution {
public:
vector<int> exchange(vector<int>& nums)
{
int i = 0, j = nums.size() - 1;
while (i < j)
{
while(i < j && (nums[i] & 1) == 1) i++;
while(i < j && (nums[j] & 1) == 0) j--;
swap(nums[i], nums[j]);
}
return nums;
}
};
作者：Krahets
链接：https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/solutions/115087/mian-shi-ti-21-diao-zheng-shu-zu-shun-xu-shi-qi-4/这题可以想到双指针方法，但一开始没有想到左右指针从左右两端开始，这种方法感觉比一段开始更好。
M45 把数组排成最小的数
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2]
输出: "102"示例 2:
输入: [3,30,34,5,9]
输出: "3033459"提示:
0 < nums.length <= 100
说明:
- 输出结果可能非常大，所以你需要返回一个字符串而不是整数
- 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0
示例：
输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。提示：
0 <= nums.length <= 500000 <= nums[i] <= 10000
题解
class Solution {
public:
string minNumber(vector<int>& nums) {
vector<string> strs;
string res;
for(int i=0;i<nums.size();i++)
strs.push_back(to_string(nums[i]));
sort(strs.begin(), strs.end(), [](string& x, string& y){ return x+y<y+x;});
for(int i=0;i<strs.size();i++)
res.append(strs[i]);
return res;
}
};
/*快排实现*/
class Solution {
public:
string minNumber(vector<int>& nums) {
vector<string> strs;
for(int i = 0; i < nums.size(); i++)
strs.push_back(to_string(nums[i]));
quickSort(strs, 0, strs.size() - 1);
string res;
for(string s : strs)
res.append(s);
return res;
}
private:
void quickSort(vector<string>& strs, int l, int r) {
if(l >= r) return;
int i = l, j = r;
while(i < j) {
while(strs[j] + strs[l] >= strs[l] + strs[j] && i < j) j--;
while(strs[i] + strs[l] <= strs[l] + strs[i] && i < j) i++;
swap(strs[i], strs[j]);
}
swap(strs[i], strs[l]);
quickSort(strs, l, i - 1);
quickSort(strs, i + 1, r);
}
};
作者：Krahets
链接：https://leetcode.cn/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/solutions/190476/mian-shi-ti-45-ba-shu-zu-pai-cheng-zui-xiao-de-s-4/快排模板
public String minNumber(int[] nums) {
String[] strs = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
strs[i] = String.valueOf(nums[i]);
}
quickSort(strs, 0, strs.length - 1);
StringBuilder res = new StringBuilder();
for (String s : strs)
res.append(s);
return res.toString();
}
public void quickSort(String[] strs, int low, int high) {
if (low < high) {
int middle = getMiddle(strs, low, high);
quickSort(strs, low, middle - 1);
quickSort(strs, middle + 1, high);
}
}
public int getMiddle(String[] strs, int low, int high) {
//数组的第一个数为基准元素
String temp = strs[low];
while (low < high) {
//从后向前找比基准小的数
while (low < high && (strs[high] + temp).compareTo(temp + strs[high]) >= 0)
high--;
//把比基准小的数移到低端
strs[low] = strs[high];
//从前向后找比基准大的数
while (low < high && (strs[low] + temp).compareTo(temp + strs[low]) <= 0)
low++;
//把比基准大的数移到高端
strs[high] = strs[low];
}
strs[low] = temp;
return low;
}51 数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5题解
class Solution {
public:
int reversePairs(vector<int>& nums) {
vector<int> tmp(nums.size());
return mergeSort(0, nums.size()-1, nums, tmp);
}
private:
int mergeSort(int l, int r, vector<int>& nums, vector<int>& tmp){
//终止条件
if(l>=r)return 0;
//递归划分
int m = (l+r)/2;
int res = mergeSort(l, m, nums, tmp) + mergeSort(m+1,r,nums,tmp);
//合并阶段
int i=l, j= m+1;//左右子数组首个元素
for(int k = l;k<=r;k++)
tmp[k]=nums[k];//辅助数组
for(int k=l;k<=r;k++){
if(i==m+1)//左子数组合并完成
nums[k]=tmp[j++];
else if(j==r+1||tmp[i]<=tmp[j])
nums[k]=tmp[i++];//排序过程
else{
nums[k]=tmp[j++];//排序过程
res+=m-i+1;//统计逆序对
}
}
return res;
}
};
