2567. Minimum Score by Changing Two Elements

LeetCode 力扣

1. Description

Given an integer array nums, define its low score as the smallest absolute difference between elements at two distinct indices, and its high score as the largest such difference.
The array’s score is the sum of its low and high scores.
You may replace two elements with any integers. Return the smallest score obtainable after these replacements.

2. Example

Example 1

Input: nums = [1,4,7,8,5]
Output: 3
Explanation: Replace nums[0] and nums[1] with 6 to obtain [6,6,7,8,5]. The equal elements give a low score of 0, and the high score is 8 - 5 = 3. The total is 3.

Example 2

Input: nums = [1,4,3]
Output: 0
Explanation: Replace nums[1] and nums[2] with 1. All elements are then equal, giving both a low score and a high score of 0.

3. Constraints

  • 3 <= nums.length <= 10$^5$
  • 1 <= nums[i] <= 10$^9$

4. Solutions

Greedy

n = nums.size()
Time complexity: O(n) on average
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int minimizeSum(vector<int> &nums) {
        const int n = nums.size();

        nth_element(nums.begin(), nums.begin() + 2, nums.end());
        sort(nums.begin(), nums.begin() + 3);
        int a = nums[0], b = nums[1], c = nums[2];

        nth_element(nums.begin(), nums.end() - 3, nums.end());
        sort(nums.end() - 3, nums.end());
        int x = nums[n - 3], y = nums[n - 2], z = nums[n - 1];

        return min({z - c, y - b, x - a});
    }
};
comments powered by Disqus