五月集训(第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; }}```![](https://img-blog.csdnimg.cn/e7a4a340e545464187653426846a3f20.png)