Skip to content

Latest commit

 

History

History
245 lines (198 loc) · 5.73 KB

README_EN.md

File metadata and controls

245 lines (198 loc) · 5.73 KB
comments difficulty edit_url rating source tags
true
Medium
1427
Weekly Contest 244 Q2
Array
Sorting

1887. Reduction Operations to Make the Array Elements Equal

中文文档

Description

Given an integer array nums, your goal is to make all elements in nums equal. To complete one operation, follow these steps:

  1. Find the largest value in nums. Let its index be i (0-indexed) and its value be largest. If there are multiple elements with the largest value, pick the smallest i.
  2. Find the next largest value in nums strictly smaller than largest. Let its value be nextLargest.
  3. Reduce nums[i] to nextLargest.

Return the number of operations to make all elements in nums equal.

 

Example 1:

Input: nums = [5,1,3]
Output: 3
Explanation: It takes 3 operations to make all elements in nums equal:
1. largest = 5 at index 0. nextLargest = 3. Reduce nums[0] to 3. nums = [3,1,3].
2. largest = 3 at index 0. nextLargest = 1. Reduce nums[0] to 1. nums = [1,1,3].
3. largest = 3 at index 2. nextLargest = 1. Reduce nums[2] to 1. nums = [1,1,1].

Example 2:

Input: nums = [1,1,1]
Output: 0
Explanation: All elements in nums are already equal.

Example 3:

Input: nums = [1,1,2,2,3]
Output: 4
Explanation: It takes 4 operations to make all elements in nums equal:
1. largest = 3 at index 4. nextLargest = 2. Reduce nums[4] to 2. nums = [1,1,2,2,2].
2. largest = 2 at index 2. nextLargest = 1. Reduce nums[2] to 1. nums = [1,1,1,2,2].
3. largest = 2 at index 3. nextLargest = 1. Reduce nums[3] to 1. nums = [1,1,1,1,2].
4. largest = 2 at index 4. nextLargest = 1. Reduce nums[4] to 1. nums = [1,1,1,1,1].

 

Constraints:

  • 1 <= nums.length <= 5 * 104
  • 1 <= nums[i] <= 5 * 104

Solutions

Solution 1

Python3

class Solution:
    def reductionOperations(self, nums: List[int]) -> int:
        nums.sort()
        ans = cnt = 0
        for i, v in enumerate(nums[1:]):
            if v != nums[i]:
                cnt += 1
            ans += cnt
        return ans

Java

class Solution {
    public int reductionOperations(int[] nums) {
        Arrays.sort(nums);
        int ans = 0, cnt = 0;
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] != nums[i - 1]) {
                ++cnt;
            }
            ans += cnt;
        }
        return ans;
    }
}

C++

class Solution {
public:
    int reductionOperations(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ans = 0, cnt = 0;
        for (int i = 1; i < nums.size(); ++i) {
            cnt += nums[i] != nums[i - 1];
            ans += cnt;
        }
        return ans;
    }
};

Go

func reductionOperations(nums []int) int {
	sort.Ints(nums)
	ans, cnt := 0, 0
	for i, v := range nums[1:] {
		if v != nums[i] {
			cnt++
		}
		ans += cnt
	}
	return ans
}

TypeScript

function reductionOperations(nums: number[]): number {
    nums.sort((a, b) => a - b);
    let ans = 0;
    let cnt = 0;
    for (let i = 1; i < nums.length; ++i) {
        if (nums[i] != nums[i - 1]) {
            ++cnt;
        }
        ans += cnt;
    }
    return ans;
}

C#

public class Solution {
    public int ReductionOperations(int[] nums) {
        Array.Sort(nums);
        int ans = 0, up = 0;
        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] != nums[i - 1]) {
                up++;
            }
            ans += up;
        }
        return ans;
    }
}

Solution 2

Python3

class Solution:
    def reductionOperations(self, nums: List[int]) -> int:
        ans = cnt = 0
        for _, v in sorted(Counter(nums).items()):
            ans += cnt * v
            cnt += 1
        return ans

Java

class Solution {
    public int reductionOperations(int[] nums) {
        Map<Integer, Integer> tm = new TreeMap<>();
        for (int v : nums) {
            tm.put(v, tm.getOrDefault(v, 0) + 1);
        }
        int ans = 0, cnt = 0;
        for (int v : tm.values()) {
            ans += cnt * v;
            ++cnt;
        }
        return ans;
    }
}

C++

class Solution {
public:
    int reductionOperations(vector<int>& nums) {
        map<int, int> m;
        for (int v : nums) ++m[v];
        int ans = 0, cnt = 0;
        for (auto [_, v] : m) {
            ans += cnt * v;
            ++cnt;
        }
        return ans;
    }
};