Given a list of integers nums, consider an operation where you pick any number e and remove every number in nums equal to e. Return the minimum number of operations required such that the length of nums is reduced by at least half.
Constraints
1 ≤ n ≤ 100,000 where n is the length of numsExample 1
Input
nums = [7, 9, 9, 7, 3, 4, 5]
Output
2
Explanation
Length of the list is 7, so we need to remove at least 4 elements. We can do this by removing all 7s and 9s.Example 2
Input
nums = [6, 6, 6, 3, 2, 1]
Output
1
Explanation
Length of the list is 6, so we need to remove at least 3 elements. We can do this by removing all 6s.Example 3
Input
nums = [1, 2, 3, 4, 5, 6]
Output
3
Explanation
We can delete any 3 numbers in the list.
Greedy Algorithm to Remove Half List
If we sort the array by the number of occurencies in non-ascending order. We then can greedily pick the numbers (that occur most) until the total picked numbers are larger than half. As we are always picking from the largest occurencies to the smallest, we can guarantee that the numbers to pick is always minimal.
1 2 3 4 5 6 7 8 9 10 11 12 13 | class Solution: def removeHalf(self, nums): d = Counter(nums) l = len(nums) x = sorted(d.values(), reverse=True) ans = 0 z = 0 for v in x: ans += 1 z += v if z * 2 >= l: break return ans |
class Solution: def removeHalf(self, nums): d = Counter(nums) l = len(nums) x = sorted(d.values(), reverse=True) ans = 0 z = 0 for v in x: ans += 1 z += v if z * 2 >= l: break return ans
The time complexity is O(NLogN) as we need to sort the array. The space complexity is O(N) as we are using Counter (or other hash map) to keep tracking the occurencies of all numbers.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Logarithm Algorithm to Compute the Power x^n Function
Next Post: Teaching Kids Programming - Algorithm to Transpose a Matrix