1338 . Reduce Array Size to The Half Leetcode || Medium || July Daily Challenge
Vložit
- čas přidán 5. 07. 2021
- Given an array arr. You can choose a set of integers and remove all the occurrences of these integers in the array.
Return the minimum size of the set so that at least half of the integers of the array are removed.
Example 1:
Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
Possible sets of size 2 are {3,5},{3,2},{5,2}.
Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has size greater than half of the size of the old array.
Only your Explaination was enough to solve the question. Thanks.
Very good explanation 🎉🎉🎉🎉
Can't we simply create another map only and insert the initial elements of map into this without using multimap
thank you @milind for asking this , in my logic, i have used another map to reverse the ordering: frequency is key now and element is value. if i create another map and not a multimap, i may run into a case where two elements have same frequency but a simple map cannot have 2 keys same, a multimap can.
Can you please tell which chrome extension you used to write over on the web page @00:33
@Samarth, I use Web Paint extension
In the test case [3,3,3,3,5,5,5,2,2,7] you remove 3 and 7 after that array size becomes 3. But in the question it is mentioned to reduced size by half. Can you please explain ??
thank you @Ashwani for asking this,
in this example, we want atleast 5 elements removed (half of ten)
if i remove only 3 ->i will still be left with 6 elements
if i remove only 5 -> i will still be left with 7 elements
if i remove both 3 & 5 then only i can remove atleast 5 elements (even though we are removing some extra elements than halfway mark, thats okay , we have no choice, we have to ensure atleast half elements are removed)
What's the difference in it.first and it->first
Saw both in your code
thank you @guman for asking this,
when i used:
for(auto it = mm.begin(); it!=mm.end();it++)
{
it->first // and other logic
}
iterator it iterates over elements of mm, it is pointing towards the element, but to get the value at which it is pointing, we need to dereference it, you can do (*it).first or it->first to get the value , both are same.
when i used:
for(auto it:m)
{
it.first // and other logic
}
i am taking help of loop to deference it, loop internally deferences & gives the value which i can use by doing: it.first (. operator is generally used to access members of object)
note: pointers and iterators have some differences, you may want to read more about them
you are in which college ? or placed at which company?
she is in iitb