Increasing leetcode - a daily topic 1403. The order of the boy sequence (greed)

Title link: https://leetcode.cn/problems/minimum-subsequence-in-non-increasing-order/

Ideas

Method 1, Greedy

The general meaning of the title is to divide the array into two sequences. The sum of the elements of one sequence is strictly greater than the sum of the elements of the other sequence, and the two requirements of the previous sequence the largest element and the shortest length are met.So it's very simple, we only need to sort the array from large to small, calculate the sum of the entire array, and then greedily take the maximum value of the array until the sum of the sequence elements is strictly greater than the sum of the other sequence elements

Code Example

func minSubsequence(nums []int) []int {sort.Slice(nums, func(i, j int) bool { return nums[i] > nums[j]})tot := 0for _, num := range nums {tot += num}for i, sum := 0, 0; ; i++ {sum += nums[i]if sum > tot-sum {return nums[:i+1]}}}

Complexity Analysis

• Time complexity: O(n logn) where n is the length of the array, sorting the array takes O(n logn) time, and traversing the array takes O(n) time
• Space complexity: O(1) No need to apply for additional space