跳转至

3774. 最大和最小 K 个元素的绝对差

题目描述

给你一个整数数组 nums 和一个整数 k。

请计算以下两者的绝对差值：

  • 数组中 k 个 最大 元素的总和；
  • 数组中 k 个 最小 元素的总和。

返回表示此差值的整数。

 

示例 1：

输入： nums = [5,2,2,4], k = 2

输出： 5

解释：

  • k = 2 个最大的元素是 4 和 5。它们的总和是 4 + 5 = 9。
  • k = 2 个最小的元素是 2 和 2。它们的总和是 2 + 2 = 4。
  • 绝对差值是 abs(9 - 4) = 5。

示例 2：

输入： nums = [100], k = 1

输出： 0

解释：

  • 最大的元素是 100。
  • 最小的元素是 100。
  • 绝对差值是 abs(100 - 100) = 0。

 

提示：

  • 1 <= n == nums.length <= 100
  • 1 <= nums[i] <= 100
  • 1 <= k <= n

解法

方法一：排序

我们首先对数组 \(\textit{nums}\) 进行排序。然后计算数组中前 \(k\) 个元素的和以及后 \(k\) 个元素的和，最后返回两者的差值。

时间复杂度 \(O(n \times \log n)\)，空间复杂度 \(O(\log n)\)，其中 \(n\) 是数组 \(\textit{nums}\) 的长度。

1
2
3
4
class Solution:
    def absDifference(self, nums: List[int], k: int) -> int:
        nums.sort()
        return sum(nums[-k:]) - sum(nums[:k])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int absDifference(int[] nums, int k) {
        Arrays.sort(nums);
        int ans = 0;
        int n = nums.length;
        for (int i = 0; i < k; ++i) {
            ans += nums[n - i - 1] - nums[i];
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int absDifference(vector<int>& nums, int k) {
        ranges::sort(nums);
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i < k; ++i) {
            ans += nums[n - i - 1] - nums[i];
        }
        return ans;
    }
};

1
2
3
4
5
6
7
func absDifference(nums []int, k int) (ans int) {
    slices.Sort(nums)
    for i := 0; i < k; i++ {
        ans += nums[len(nums)-i-1] - nums[i]
    }
    return
}

1
2
3
4
5
6
7
8
function absDifference(nums: number[], k: number): number {
    nums.sort((a, b) => a - b);
    let ans = 0;
    for (let i = 0; i < k; ++i) {
        ans += nums.at(-i - 1)! - nums[i];
    }
    return ans;
}

评论