Leetcode Problem:
Summary
- The problem is to find the minimum number of operations needed to make the elements in the array distinct
- The operation allowed is to remove 3 elements from the beginning of the array
- The goal is to return the minimum number of operations required to make all elements in the array distinct.
Approach
- The approach used is to first count the occurrences of each number in the array
- Then, if a number occurs more than once, we find the last occurrence of that number and calculate the minimum number of operations required to remove all occurrences of that number
- The minimum number of operations is calculated by dividing the last occurrence index by 3 and adding 1.
Complexity
- O(n) where n is the size of the array, because we are scanning the array once to count the occurrences of each number.
Explanation
- The code first initializes a count array `numberCnt` to keep track of the occurrences of each number in the array
- It then scans the array from the end to the beginning and increments the count of each number in the `numberCnt` array
- If a number occurs more than once, it updates the `lastIdx` variable to the last occurrence index of that number
- Finally, it calculates the minimum number of operations required by dividing the `lastIdx` by 3 and adding 1, and returns this value.
Solution Code:
class Solution {
public:
int numberCnt[101];
int minimumOperations(vector& nums) {
int lastIdx = -1;
for(int i = nums.size() - 1 ; i >= 0 ; i--){
numberCnt[nums[i]]++;
if(numberCnt[nums[i]] >= 2){
lastIdx = i;
break;
}
}
if(lastIdx == -1) return 0;
return lastIdx / 3 + 1;
}
};
'알고리즘' 카테고리의 다른 글
| Count the Number of Powerful Integers (0) | 2025.04.11 |
|---|---|
| Minimum Operations to Make Array Values Equal to K (0) | 2025.04.10 |
| Partition Equal Subset Sum (0) | 2025.04.08 |
| Largest Divisible Subset (0) | 2025.04.06 |
| Sum of All Subset XOR Totals (0) | 2025.04.05 |
짬뽕얼큰하게
