912. Sort array

Merge

def sortArray(self, nums: List[int]) -> List[int]:
        def merge_sort(nums, l, r):
            # Termination conditions
            if l >= r: return
            # Recursive partition array
            m = (l + r) // 2
            merge_sort(nums, l, m)
            merge_sort(nums, m + 1, r)
            # Merge subarrays
            tmp = nums[l:r + 1]       # Temporary storage of interval elements to be merged
            i, j = 0, m - l + 1       # The two pointers point to the first element of the left / right sub array respectively
            for k in range(l, r + 1): # Traverse and merge left / right subarrays
                if i == m - l + 1:
                    nums[k] = tmp[j]
                    j += 1
                elif j == r - l + 1 or tmp[i] <= tmp[j]:
                    nums[k] = tmp[i]
                    i += 1
                else:
                    nums[k] = tmp[j]
                    j += 1
        merge_sort(nums, 0, len(nums)-1)
        return nums

Summary: to be honest, I still remember the idea of merging and sorting in a week, but I have forgotten 80% of the specific code. After reading the answer of God K, I know I can't write it now. You need to write it again before you can remember it clearly. I even review quickly, rather than passing through the knowledge points one by one. After one, understand one and count one. Human nature is to be greedy for more and faster, which is not surprising. I feel that my willpower and physical fitness are almost to the limit. If I want to review 10 questions today, it is impossible to merge them now. So I decided to take a break and write it down tomorrow. Because I think if the interviewer asks about merging or quick scheduling, it's definitely not to let us write a new one, but will ask us some very specific details. If we don't understand it thoroughly, it's likely to fail. During the interview, there must be many details. If I am careless in my study or review, I will not be able to go to the best company. This is certain. If you want to go to the best company, you have to pay 120% of your efforts.

Quick row

def findKthLargest(self, nums: List[int], k: int) -> int:

        def quicksort(left, right, nums):
            if left >= right: return 
            pivot = nums[left]
            start, end = left, right
            while left < right:
                while left < right and nums[right] > pivot: right -= 1
                while left < right and nums[left] < pivot: left += 1
                nums[left], nums[right] = nums[right], nums[left]
            nums[left], pivot = pivot, nums[left]
            quicksort(start, right-1, nums)
            quicksort(left+1, end, nums)

        quicksort(0, len(nums)-1, nums)
        return nums[-k]    

Summary of experience: I really can't remember how to do it today. But now I can remember after reading the code. I'm going to go over all the sorting carefully tomorrow.

215. The kth largest element in the array

Given the integer array nums and integer k, please return the K largest element in the array.
Please note that you need to find the K largest element after the array is sorted, not the k different element.

import heapq
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        que = []
        heapq.heapify(que)
        for num in nums:
            heapq.heappush(que, num)
            if len(que) > k:
                heapq.heappop(que)
        return que[0]

Summary of experience: for the previous code, the method I used was fast scheduling. I've been familiar with the big top pile used this time, and it's much faster as expected.

315. Calculate the number of elements on the right that are smaller than the current element

class Solution:
    def countSmaller(self, nums) -> List[int]:
        def merge(left, right, nums, res, temp, index):

            if left >= right: return
            mid = (left + right) // 2
            merge(0, mid, nums, res, temp, index)
            merge(mid+1, right, nums, res, temp, index)
            if nums[index[mid]] <= nums[index[mid + 1]]:
                return

            # merge
            for i in range(left, right + 1):
                temp[i] = index[i]

            i, j = left, mid - left + 1
            for k in range(left, right + 1):
                if i > mid:
                    index[k] = temp[j]
                    j += 1
                elif j > right:
                    index[k] = temp[i]
                    i += 1
                    res[index[k]] += (right - mid)
                elif nums[temp[i]] <= nums[temp[j]]:
                    index[k] = temp[i]
                    i += 1
                    res[index[k]] += (j - mid - 1)
                else:
                    index[k] = temp[j]
                    j += 1

        size = len(nums)
        if size == 0:
            return []
        elif size == 1:
            return nums[0]
        res = [0 for _ in range(size)]
        temp = [None for _ in range(size)]
        index = [i for i in range(size)]

        merge(0, size-1, nums, res, temp, index)
        return res

Summary of experience: this problem is difficult. I remember to use reverse order pairs when writing, but I'm still not good at using index arrays. I didn't understand it at that time. I still can't write it now. It seems that what I said before is right. If I don't understand it, I'll never write it. I read the reference answer several times and understood it better than the last time. But I still can't write it in one breath.

from typing import List


class Solution:

    def countSmaller(self, nums: List[int]) -> List[int]:
        size = len(nums)
        if size == 0:
            return []
        if size == 1:
            return [0]

        temp = [None for _ in range(size)]
        res = [0 for _ in range(size)]
        # Index array, function: when merging back, it is convenient to know which subscript element it is
        indexes = [i for i in range(size)]

        self.__merge_and_count_smaller(nums, 0, size - 1, temp, indexes, res)
        return res

    def __merge_and_count_smaller(self, nums, left, right, temp, indexes, res):
        if left == right:
            return
        mid = left + (right - left) // 2
        self.__merge_and_count_smaller(nums, left, mid, temp, indexes, res)
        self.__merge_and_count_smaller(nums, mid + 1, right, temp, indexes, res)

        if nums[indexes[mid]] <= nums[indexes[mid + 1]]:
            return
        self.__sort_and_count_smaller(nums, left, mid, right, temp, indexes, res)

    def __sort_and_count_smaller(self, nums, left, mid, right, temp, indexes, res):
        # [left,mid] pre ordered array
        # [mid+1,right] post ordered array

        # Copy first, then merge
        for i in range(left, right + 1):
            temp[i] = indexes[i]

        i = left
        j = mid + 1
        for k in range(left, right + 1):
            if i > mid:
                indexes[k] = temp[j]
                j += 1
            elif j > right:
                indexes[k] = temp[i]
                i += 1
                res[indexes[k]] += (right - mid)
            elif nums[temp[i]] <= nums[temp[j]]:
                indexes[k] = temp[i]
                i += 1
                res[indexes[k]] += (j - mid - 1)
            else:
                indexes[k] = temp[j]
                j += 1


if __name__ == '__main__':
    nums = [5, 2, 6, 1]
    solution = Solution()
    result = solution.countSmaller(nums)
    print(result)

After walking through the answer debug, I can understand it, but I don't quite understand it when count ing times. In addition, the index is still a little confused. Skip first. Go back and do it again.

53. Maximum subarray and

Give you an integer array nums. Please find a continuous sub array with the largest sum (the sub array contains at least one element) and return its maximum sum.
A subarray is a contiguous part of an array.

def maxSubArray(self, nums: List[int]) -> int:
        if not nums: return
        if len(nums) == 1: return nums[0]
        res, total = [], 0
        flag = None
        for num in nums:
            total += num
            if total < 0:
                total = 0
                continue
            else:
                flag = True
                res.append(total)
        return max(res) if flag else max(nums)

I still remember that this solution should be simple dynamic programming, but the topic says that recursive method can also be used. As for the case of negative numbers, I also thought carefully. If there is a positive number, it will return to that positive number in the end. If they are all negative numbers, the largest negative number will be returned. I used flag as a flag.

I read the recursive method and didn't understand it very well.

class Solution {
public:
    struct Status {
        int lSum, rSum, mSum, iSum;
    };

    Status pushUp(Status l, Status r) {
        int iSum = l.iSum + r.iSum;
        int lSum = max(l.lSum, l.iSum + r.lSum);
        int rSum = max(r.rSum, r.iSum + l.rSum);
        int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);
        return (Status) {lSum, rSum, mSum, iSum};
    };

    Status get(vector<int> &a, int l, int r) {
        if (l == r) {
            return (Status) {a[l], a[l], a[l], a[l]};
        }
        int m = (l + r) >> 1;
        Status lSub = get(a, l, m);
        Status rSub = get(a, m + 1, r);
        return pushUp(lSub, rSub);
    }

    int maxSubArray(vector<int>& nums) {
        return get(nums, 0, nums.size() - 1).mSum;
    }
};