1.977. 有序数组的平方
不追求很高的时间复杂度的化我们就对数组进行原地修改并排序即可。
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
for(int i=0;i<nums.size();i++){
nums[i]*=nums[i];
}
sort(nums.begin(),nums.end());
return nums;
}
};
2.268. 丢失的数字
给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
示例 1：
输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 2：
输入：nums = [0,1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 3：
输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。
示例 4：
输入：nums = [0]
输出：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。
提示：
n == nums.length
1 <= n <= 104
0 <= nums[i] <= n
nums 中的所有数字都 独一无二
使用排序的做法非常简单，对原数组进行排序然后对照下标即可，因为数组中的数组是从[0,n]排序之后找到第一个与下标不等的元素返回即可。
class Solution {
public:
int missingNumber(vector<int>& nums) {
sort(nums.begin(),nums.end());
for(int i=0;i<nums.size();i++){
if(i!=nums[i]){
return i;
}
}
return nums.size();
}
};
当然也有更优的时间复杂度，又观察到题目告诉我们数组元素均是独一无二的，那么我们就可以先算出[0，n]这些数字的和，然后减去数组中元素和，那么剩下的就是缺失的元素。
class Solution {
public:
int missingNumber(vector<int>& nums) {
int n=nums.size();
int sum=(1+n)*n/2;
for(int i=0;i<n;i++){
sum-=nums[i];
}
return sum;
}
};
3.1877. 数组中最大数对和的最小值
一个数对 (a,b) 的 数对和 等于 a + b 。最大数对和 是一个数对数组中最大的 数对和 。
比方说，如果我们有数对 (1,5) ，(2,3) 和 (4,4)，最大数对和 为 max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8 。
给你一个长度为 偶数 n 的数组 nums ，请你将 nums 中的元素分成 n / 2 个数对，使得nums 中每个元素 恰好 在 一个 数对中，且
最大数对和 的值 最小 。
请你在最优数对划分的方案下，返回最小的 最大数对和 。
示例 1：
输入：nums = [3,5,2,3]
输出：7
解释：数组中的元素可以分为数对 (3,3) 和 (5,2) 。
最大数对和为 max(3+3, 5+2) = max(6, 7) = 7 。
示例 2：
输入：nums = [3,5,4,2,4,6]
输出：8
解释：数组中的元素可以分为数对 (3,5)，(4,4) 和 (6,2) 。
最大数对和为 max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8 。
这道题更像是贪心，不过我们的贪心策略就是利用排序。题目要求我们找出最小的最大数对和，那么如何找到最大数对和？很简单，将数组划分为若干数对之后找出最大值就行，对于这个过程如果没有要求我们找出最小的最大数对和，完全可以吧数组最大和第二大元素相加并返回。但问题是如何找到最小的最大数对和。
首先最小的最大数对和就是指吧数组中的配对情况都列出后我们返回最小的最大数对和。我们先满足最小，这就很简单了，要想使得数对和最小，我们吧数组进行升序排序，再不断遍历让当前遍历到的较大元素加上较小元素即可，并不断维护最大值。至于为何这样是最小的数对和可以利用基本不等式证明，这里就不再解释了。
class Solution {
public:
int minPairSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
int ans=0;
for(int i=0;i<nums.size()/2;++i){
ans=max(ans,nums[i]+nums[nums.size()-i-1]);
}
return ans;
}
};
4.950. 按递增顺序显示卡牌
牌组中的每张卡牌都对应有一个唯一的整数。你可以按你想要的顺序对这套卡片进行排序。
最初，这些卡牌在牌组里是正面朝下的（即，未显示状态）。
现在，重复执行以下步骤，直到显示所有卡牌为止：
从牌组顶部抽一张牌，显示它，然后将其从牌组中移出。
如果牌组中仍有牌，则将下一张处于牌组顶部的牌放在牌组的底部。
如果仍有未显示的牌，那么返回步骤 1。否则，停止行动。
返回能以递增顺序显示卡牌的牌组顺序。
答案中的第一张牌被认为处于牌堆顶部。
示例：
输入：[17,13,11,2,3,5,7]
输出：[2,13,3,11,5,17,7]
解释：
我们得到的牌组顺序为 [17,13,11,2,3,5,7]（这个顺序不重要），然后将其重新排序。
重新排序后，牌组以 [2,13,3,11,5,17,7] 开始，其中 2 位于牌组的顶部。
我们显示 2，然后将 13 移到底部。牌组现在是 [3,11,5,17,7,13]。
我们显示 3，并将 11 移到底部。牌组现在是 [5,17,7,13,11]。
我们显示 5，然后将 17 移到底部。牌组现在是 [7,13,11,17]。
我们显示 7，并将 13 移到底部。牌组现在是 [11,17,13]。
我们显示 11，然后将 17 移到底部。牌组现在是 [13,17]。
我们展示 13，然后将 17 移到底部。牌组现在是 [17]。
我们显示 17。
由于所有卡片都是按递增顺序排列显示的，所以答案是正确的。
这道题刚开始读起来是十分饶的，其实题目要让我们求的就是一个按照他要求的规则拿牌之后拿到的是一个递增顺序的顺序序列。对比示例并且按照他的规则拿牌即可看出。
但是直接找到这样一个序列肯定是十分麻烦的，我们转换一下思路。假如现在我们的序列就是一个升序的序列，也就是按照答案和规则拿到的序列，我们要做的就是找到它是由哪个序列拿到的即可，听上去是不是跟之前的思路没什么两样，但是这却是十分简单的思路。
首先我们将数组进行升序排序，并且定义一个记录原始下标的位置。然后对下标数组按规则进行拿牌。之后我们得到了新的下标数组:tmp,接下来你可能会问这一步的意义是什么。
首先我们要明白一点，对下标数组进行按规则拿牌是针对所有的顺序的并不是单一的原数组顺序或者是答案顺序，也就是说任何一个数组按照这个规则拿牌之后他所对应的下标数组就是我们的tmp数组.自然而然的对于答案数组，按照所得到的tmp数组映射就是升序序列。这是一个双射的关系，可以互相映射。
现在我们假设我们拿牌的牌组就是答案数组，接下来要做的就是对这个答案数组按照规则拿完牌之后的序列也就是我们的升序序列按照下标关系映射回去即可.
class Solution {
public:
vector<int> deckRevealedIncreasing(vector<int>& deck) {
vector<int> ans,index,tmp;
for(int i=0;i<deck.size();i++){
index.push_back(i);
}
sort(deck.begin(),deck.end());
int l=0,r=deck.size()-1;
while(l<=r){
tmp.push_back(index[l]);
l++;
if(l>r){
break;
}
index.push_back(index[l]);
r++;
l++;
}
for(int i=0;i<deck.size();i++){
ans.push_back(0);
}
for(int i=0;i<deck.size();i++){
ans[tmp[i]]=deck[i];
}
return ans;
}
};
