3684-MaximizeSumOfAtMostKDistinctElements.go

package main

// 3684. Maximize Sum of At Most K Distinct Elements
// You are given a positive integer array nums and an integer k.

// Choose at most k elements from nums so that their sum is maximized. However, the chosen numbers must be distinct.

// Return an array containing the chosen numbers in strictly descending order.

// Example 1:
// Input: nums = [84,93,100,77,90], k = 3
// Output: [100,93,90]
// Explanation:
// The maximum sum is 283, which is attained by choosing 93, 100 and 90. We rearrange them in strictly descending order as [100, 93, 90].

// Example 2:
// Input: nums = [84,93,100,77,93], k = 3
// Output: [100,93,84]
// Explanation:
// The maximum sum is 277, which is attained by choosing 84, 93 and 100. We rearrange them in strictly descending order as [100, 93, 84]. We cannot choose 93, 100 and 93 because the chosen numbers must be distinct.

// Example 3:
// Input: nums = [1,1,1,2,2,2], k = 6
// Output: [2,1]
// Explanation:
// The maximum sum is 3, which is attained by choosing 1 and 2. We rearrange them in strictly descending order as [2, 1].

// Constraints:
//     1 <= nums.length <= 100
//     1 <= nums[i] <= 10^9
//     1 <= k <= nums.length

import "fmt"
import "sort"
import "slices"

func maxKDistinct(nums []int, k int) []int {
    set := make(map[int]bool)
    for _, v := range nums {
        set[v] = true
    }
    arr := make([]int, 0, len(set))
    for v := range set {
        arr = append(arr, v)
    }
    sort.Slice(arr, func(i, j int) bool {
        return arr[i] > arr[j]
    })
    if k > len(arr) {
        k = len(arr)
    }
    return arr[:k]
}

func maxKDistinct1(nums []int, k int) []int {
    slices.SortFunc(nums, func(a, b int) int { return b - a })
    nums = slices.Compact(nums) // 原地去重
    if len(nums) > k {
        return nums[:k]
    }
    return nums
}

func main() {
    // Example 1:
    // Input: nums = [84,93,100,77,90], k = 3
    // Output: [100,93,90]
    // Explanation:
    // The maximum sum is 283, which is attained by choosing 93, 100 and 90. We rearrange them in strictly descending order as [100, 93, 90].
    fmt.Println(maxKDistinct([]int{84,93,100,77,90}, 3)) // [100,93,90]
    // Example 2:
    // Input: nums = [84,93,100,77,93], k = 3
    // Output: [100,93,84]
    // Explanation:
    // The maximum sum is 277, which is attained by choosing 84, 93 and 100. We rearrange them in strictly descending order as [100, 93, 84]. We cannot choose 93, 100 and 93 because the chosen numbers must be distinct.
    fmt.Println(maxKDistinct([]int{84,93,100,77,93}, 3)) // [100,93,84]
    // Example 3:
    // Input: nums = [1,1,1,2,2,2], k = 6
    // Output: [2,1]
    // Explanation:
    // The maximum sum is 3, which is attained by choosing 1 and 2. We rearrange them in strictly descending order as [2, 1].
    fmt.Println(maxKDistinct([]int{84,93,100,77,9}, 6)) // [2,1]

    fmt.Println(maxKDistinct([]int{1,2,3,4,5,6,7,8,9}, 2)) // [9,8]
    fmt.Println(maxKDistinct([]int{9,8,7,6,5,4,3,2,1}, 2)) // [9,8]

    fmt.Println(maxKDistinct1([]int{84,93,100,77,90}, 3)) // [100,93,90]
    fmt.Println(maxKDistinct1([]int{84,93,100,77,93}, 3)) // [100,93,84]
    fmt.Println(maxKDistinct1([]int{84,93,100,77,9}, 6)) // [2,1]
    fmt.Println(maxKDistinct1([]int{1,2,3,4,5,6,7,8,9}, 2)) // [9,8]
    fmt.Println(maxKDistinct1([]int{9,8,7,6,5,4,3,2,1}, 2)) // [9,8]
}