五月集训（第3天）——排序
一. 思路代码以及结果
977. 有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
测试用例较小这里直接原地平方后排序即可。class Solution { public int[] sortedSquares(int[] nums) { for(int i = 0;i < nums.length;i++){ nums[i] *= nums[i]; } Arrays.sort(nums); return nums; }}
268. 丢失的数字
给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
先说一种比较取巧的方法，我们知道可以利用位运算的特殊性找出落单的数字:a ^ a^b=b;因此先将越界的值送给ans，然后遍历数组，将每个数字与ans^,然后，再将ans与0——n-1^;使丢失的数出现一次，其他的数出现两次。class Solution { public int missingNumber(int[] nums) { int ans = nums.length; for(int i = 0;i < nums.length;i++){ ans ^= nums[i]; ans ^= i; } return ans; }}
正常的思路应该是对数组进行排序，遍历查看0-n-1没有哪个数
class Solution { public int missingNumber(int[] nums) { Arrays.sort(nums); for(int i = 0;i < nums.length;i++){ if(nums[i] != i){ return i; } } return nums.length; }}
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 中每个元素 恰好 在 一个 数对中，且 最大数对和 的值 最小 。 请你在最优数对划分的方案下，返回最小的 最大数对和 。
这题依靠数学直接很容易写出，难点在于证明，这里我就不写了，将数组排序后，直接贪心将最大数对和找出。class Solution { public int minPairSum(int[] nums) { Arrays.sort(nums); int i = 0,j = nums.length-1; int ans = nums[i++] + nums[j--]; while(i < j){ int temp = nums[i++] + nums[j--]; if(ans < temp){ ans = temp; } } return ans; }}
950. 按递增顺序显示卡牌
牌组中的每张卡牌都对应有一个唯一的整数。你可以按你想要的顺序对这套卡片进行排序。
最初，这些卡牌在牌组里是正面朝下的（即，未显示状态）。
现在，重复执行以下步骤，直到显示所有卡牌为止：
从牌组顶部抽一张牌，显示它，然后将其从牌组中移出。 如果牌组中仍有牌，则将下一张处于牌组顶部的牌放在牌组的底部。
如果仍有未显示的牌，那么返回步骤 1。否则，停止行动。 返回能以递增顺序显示卡牌的牌组顺序。答案中的第一张牌被认为处于牌堆顶部。
模拟题，我们按照题中给的抽取顺序，将排序后的数组反过来进行模拟即可：也就是将队尾的牌拿出来放到队首，然后将移除的数拿回来放在队首。class Solution { public int[] deckRevealedIncreasing(int[] deck) { Arrays.sort(deck); int n = deck.length; Deque<Integer> d = new ArrayDeque<>(); d.addFirst(deck[n - 1]); for (int i = deck.length - 2; i >= 0; i--) { int end = d.pollLast(); d.addFirst(end); d.addFirst(deck[i]); } int k = 0, res[] = new int[n]; for (int x : d) { res[k++] = x; } return res; }}```