五月刷题03——排序

今日刷题内容： 排序

前言

• 更新每天刷题的题解内容
• 注重个人理解，看难度更新题目数量
• 题目来源于力扣
• 新开专栏，争取每日都能做出至少一题=v=
• 语言java、python、c\c++

---

一、今日题目

1. 977. 有序数组的平方*****
2. 268. 丢失的数字*****
3. 1877. 数组中最大数对和的最小值*****
4. 950. 按递增顺序显示卡牌*****

二、解题思路

1. 977. 有序数组的平方*****

1. 可以直接求每个元素的平方
2. 排序后即可得到结果

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        ret = [i * i for i in nums]
        ret.sort()
        return ret

---

2. 268. 丢失的数字*****

1. 已知是从[0, n]的数，所以排序后比较元素和下标的值即可
2. 如果元素和下标值不匹配说明该下标就是要找的值
3. 否则返回数组的长度

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        nums.sort()
        ret = len(nums)
        for idx, val in enumerate(nums):
            if idx != val:
                ret = idx
                break
        
        return ret

---

3. 1877. 数组中最大数对和的最小值*****

1. 根据题意，数对和是指当前数组的最大值和最小值之和
2. 即从数组中取数，不可重复取
3. 维护一个最大值即可

class Solution {
    
    public int minPairSum(int[] nums) {
    
        Arrays.sort(nums);
        int i = 0;
        int n = nums.length;
        int ret = 0;
        for(i = 0; i < n / 2; i++){
    
            ret = Math.max(ret, nums[i] + nums[n - i - 1]);
        }
        return ret;
    }
}

---

4. 950. 按递增顺序显示卡牌*****

1. 模拟可知，每次放的大小按0， 2， 4，……的规律放牌
2. 即根据下标模拟，每次放完牌后，将下一个下标放到队尾
3. 重复以上过程即可

class Solution:
    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:
        
        n = len(deck)
        # 维护一个下标队列
        mark = [i for i in range(n)]
        deck.sort()
        ret = [0 for i in range(n)]
        for card in deck:
            ret[ mark.pop(0) ] = card
            if mark:
            # 如果下标队列不为空，将队首元素移到队尾
                mark.append(mark.pop(0))
                
        return ret