'2025/04/10'에 해당되는 글 1건

Leetcode Problem:

• Minimum Operations to Make Array Values Equal to K

Summary

• The problem requires to find the minimum number of operations required to make every element in the array equal to a given number k
• An operation is defined as selecting a valid integer h for the current values in the array, and for each index i where nums[i] > h, set nums[i] to h.

Approach

• The solution sorts the input array and checks if the first element is less than k
• If it is, the function returns -1
• Otherwise, it initializes a counter cnt and a variable cur to the first element of the array
• It then iterates over the array, incrementing cnt whenever it encounters an element different from cur
• Finally, it returns cnt as the minimum number of operations required.

Complexity

• O(n log n) due to the sorting operation, where n is the size of the input array.

Explanation

• The provided solution code uses a simple and efficient approach to solve the problem
• First, it sorts the input array in ascending order
• If the first element is less than k, the function returns -1, indicating that it is impossible to make all elements equal to k
• Otherwise, it initializes a counter cnt and a variable cur to the first element of the array
• It then iterates over the array, incrementing cnt whenever it encounters an element different from cur
• Finally, it returns cnt as the minimum number of operations required
• The time complexity of this solution is O(n log n) due to the sorting operation, where n is the size of the input array.

Solution Code:

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