Easy

题目描述

给你一个整数数组 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

解题思路

这道题的核心思路是找到数组中最大的 k 个元素和最小的 k 个元素，然后计算它们的绝对差值。

解法分析：

最直观的方法是对数组进行排序。排序后，前 k 个元素就是最小的 k 个元素，后 k 个元素就是最大的 k 个元素。

具体步骤：

  1. 对数组 nums 进行升序排序
  2. 计算前 k 个元素的和（最小的 k 个元素）
  3. 计算后 k 个元素的和（最大的 k 个元素）
  4. 返回两者的绝对差值

这种方法的优势在于实现简单，逻辑清晰。由于题目的数据规模较小（n ≤ 100），排序的时间复杂度完全可以接受。

其他解法思考：

  • 可以使用堆（优先队列）来找到最大和最小的 k 个元素，但在数据规模较小的情况下，排序方法更简洁高效。
  • 也可以使用快速选择算法，但同样在小规模数据下，排序已经足够优秀。

因此，排序方法是这道题的最佳解法，既简单又高效。

代码实现

class Solution {
public:
    int absDifference(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        
        int minSum = 0, maxSum = 0;
        int n = nums.size();
        
        for (int i = 0; i < k; i++) {
            minSum += nums[i];
            maxSum += nums[n - 1 - i];
        }
        
        return abs(maxSum - minSum);
    }
};

class Solution:
    def absDifference(self, nums: List[int], k: int) -> int:
        nums.sort()
        
        min_sum = sum(nums[:k])
        max_sum = sum(nums[-k:])
        
        return abs(max_sum - min_sum)

public class Solution {
    public int AbsDifference(int[] nums, int k) {
        Array.Sort(nums);
        
        int minSum = 0, maxSum = 0;
        int n = nums.Length;
        
        for (int i = 0; i < k; i++) {
            minSum += nums[i];
            maxSum += nums[n - 1 - i];
        }
        
        return Math.Abs(maxSum - minSum);
    }
}

var absDifference = function(nums, k) {
    nums.sort((a, b) => a - b);
    
    let minSum = 0, maxSum = 0;
    const n = nums.length;
    
    for (let i = 0; i < k; i++) {
        minSum += nums[i];
        maxSum += nums[n - 1 - i];
    }
    
    return Math.abs(maxSum - minSum);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度值
时间复杂度O(n log n)
空间复杂度O(1)

说明：

  • 时间复杂度：主要由排序操作决定，为 O(n log n)，其中 n 是数组长度
  • 空间复杂度：除了输入数组外，只使用了常数个额外变量，为 O(1)