数组排序问题-LeetCode 905、922、1122、451（哈希表，双指针）
数组排序问题-LeetCode 905、922、1122、451（哈希表，双指针）
编程题
【LeetCode #905】按奇偶排序数组
给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素。 你可以返回满足此条件的任何数组作为答案。
示例： 输入：[3,1,2,4] 输出：[2,4,3,1] 输出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也会被接受。
解题思路：
使用双指针left和right，如果left指向数值为偶数，则向右移动，如果right指向的数值为奇数则向左移动，如果两个同时不满足，那就交换两个数值的位置！
class Solution {
public:
vector<int> sortArrayByParity(vector<int>& A) {
if(A.size() == 0) return A;
int l = 0, r = A.size()-1;
while(l < r){
if((A[l] & 1) == 0){
l++;
}else if((A[r] & 1) == 1){
r--;
}else{
swap(A[l], A[r]);
l++;
r--;
}
}
return A;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sort-array-by-parity
【LeetCode #922】按奇偶排序数组 II
给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。 对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。 你可以返回任何满足上述条件的数组作为答案。
示例： 输入：[4,2,5,7] 输出：[4,5,2,7] 解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。
解题思路：
与上一题一样的思路，不过此时的双指针不再是头尾指针，而是奇偶索引指针，即一个指向奇索引，另外一个指向偶索引。然后判断其值得奇偶情况即可！
class Solution {
public:
vector<int> sortArrayByParityII(vector<int>& A) {
int even = 0, odd = 1;
while(odd < A.size() && even < A.size()){
if((A[even] & 1) == 0){
even += 2;
}else if((A[odd] & 1) == 1){
odd += 2;
}else{
swap(A[even], A[odd]);
even += 2;
odd += 2;
}
}
return A;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sort-array-by-parity-ii
【LeetCode #1122】数组的相对排序
给你两个数组，arr1 和 arr2，
- arr2 中的元素各不相同
- arr2 中的每个元素都出现在 arr1 中 对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
示例： 输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6] 输出：[2,2,2,1,4,3,3,9,6,7,19]
解题思路：
使用计数排序的方法，首先遍历记录arr1中各个元素的个数，然后以arr2中的元素为key，将其中元素按照相对顺序写入到res中，同时将记录数减一。那么剩余的不在arr2中的元素记录数一定不为零。然后将其排序写入res中即可！
class Solution {
public:
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
map<int, int> counter;
vector<int> res;
vector<int> left; //剩余的数
for(auto i: arr1){
counter[i]++;
}
for(auto i: arr2){
if(counter.count(i)){
while(counter[i] > 0){
res.push_back(i);
counter[i] -= 1;
}
}
}
for(auto i: arr1){
if(counter[i] != 0){
while(counter[i] > 0){
left.push_back(i);
counter[i] -= 1;
}
}
}
sort(left.begin(), left.end());
for(auto i: left){
res.push_back(i);
}
return res;
}
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/relative-sort-array
【LeetCode #451】根据字符出现频率排序
给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
示例 1: 输入: "tree" 输出: "eert"
解释: 'e'出现两次，'r'和't'都只出现一次。 因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
解题思路：
这个思路就很简单，重要是STL库的使用，如何对unordered_map按照value来排序，默认是按照key来排序的！由于STL中的泛用sort需要随机访问迭代器，因此只有拷贝到vector中才可以实现排序！但是用哈希表计数很快的哦！
class Solution {
public:
string frequencySort(string s) {
map<char, int> hashmap;
string res = "";
if(s.length() <= 1) return res;
for(auto c: s){
hashmap[c]++;
}
vector<pair<char, int>> vec(hashmap.begin(), hashmap.end());
//sort需要随机访问迭代器，显然map没有这种形式，需要使用vec存储
sort(vec.begin(), vec.end(), [](const pair<char, int>& a, const pair<char, int>& b){
return a.second > b.second;
});
for(auto it: vec){
while(it.second--){
res += it.first;
}
}
return res;
}
};腾讯云开发者
