May brush question 03 - sorting

Today's brush topic content ： Sort

Preface

• Update the problem solution content of the problem brush every day
• Focus on personal understanding , Look at the difficulty and update the number of questions
• The title comes from Li Kou
• New column , Try to work out at least one question every day =v=
• Language java、python、c\c++

---

One 、 Today's topic

1. 977. The square of an ordered array *****
2. 268. Missing numbers *****
3. 1877. The minimum value of the sum of the largest pairs in an array *****
4. 950. Display cards in ascending order *****

Two 、 Their thinking

1. 977. The square of an ordered array *****

1. You can directly find the square of each element
2. After sorting, you can get the result

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

---

2. 268. Missing numbers *****

1. Known from [0, n] Number of numbers , So compare the values of elements and subscripts after sorting
2. If the element and the subscript value do not match, the subscript is the value to be found
3. Otherwise, return the length of the array

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. The minimum value of the sum of the largest pairs in an array *****

1. According to the meaning , The sum of pairs refers to the sum of the maximum and minimum values of the current array
2. That is, get data from the array , Can not be repeated
3. Maintain a maximum value

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. Display cards in ascending order *****

1. Simulation shows that , The size of each time is 0, 2, 4,…… Play cards regularly
2. That is, simulate according to the subscript , After each play , Put the next subscript at the end of the team
3. Repeat the above process

class Solution:
    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:
        
        n = len(deck)
        #  Maintain a subscript queue 
        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:
            #  If the subscript queue is not empty , Move the first element of the team to the end of the team 
                mark.append(mark.pop(0))
                
        return ret