How to remove 1 frequency of an element form a Map?-CodePudding

I was attempting this question in a Test.

It asked to make sure that an array could hold maximum of 2 repeated elements, if any element is occurring more than twice, that should be removed.

Given -    [2, 2, 2, 3, 4, 4, 5]
Expected - [2, 2, 3, 4, 4, 5]

So, I tried with this approach as follows -

// 1. HashMap to count frequency of each element Key - Element, Value - Frequency
Map<Integer, Integer> data = new HashMap<Integer, Integer>();
for(int index = 0; index < n; index  ) {
    if(data.containsKey(arr[index])) {
        data.put(arr[index], data.get(arr[index])   1);
    }
    else {
        data.put(arr[index], 1);
    }
}

// 2. Find most frequent element
int max_count = 0, need_to_remove = 0;
for(Entry<Integer, Integer> value : data.entrySet()) {
    if(max_count < value.getValue()) {
        need_to_remove = value.getKey();
        max_count = value.getValue();
    }
}
        
System.out.println("Max Count: "   max_count   " , Remove one occurrence of: "   need_to_remove);
//Output - Max Count: 3 , Remove one occurrence of : 2

Since, Value - 2 with Frequency - 3, need to remove a '2' from the map

// 3. Remove 'need_to_remove' value from map
map.remove(need_to_remove);

But doing so, it removes all occurrences of Element - 2 from map.

{3=1, 4=2, 5=1}

I'm not really sure, about what needs to be done from here.

CodePudding user response：

Create a new, empty list (lets call it dest) and a Map of value and frequency (lets call this one freq).

Populate the dest list by iterating over the data list.

As you iterate over the list, update freq and increment the value of the key that corresponds to the value in data.

If freq.get(value) is greater than 2, then don't copy it to dest.

Once you have completely iterated over the data list, dest should contain the values with no more than 2 instances of a given value.

Additionally, freq should contain the total count of the number of times that the key occurred in data.

This makes it so that you don't need to mutate the data list in place - you're just copying it and only copying at most 2 of a given value.

CodePudding user response：

The java.util.HashMap.remove() is used to remove the mapping of any particular key from the map. It basically removes the values for any particular key in the Map. https://www.geeksforgeeks.org/hashmap-remove-method-in-java/

assuming that map is your data hashMap. and you want to reduce the count of value in your key, here is 2. so you should set the value again by getting the value and reducing it. like this

map.put(key, map.get(key) - 1);

however you should remove one key in your arr. instead of your map.

int need_to_remove_index = arr.indexOf(need_to_remove);
arr.remove(need_to_remove_index);

CodePudding user response：

If the input is a list, the frequency map should be used just to track the number of occurrences using method Map::merge. The repeated elements can be removed from the list if an iterator is used to traverse the list, and Iterator has method remove():

List<Integer> list = new ArrayList<>(Arrays.asList(2, 2, 2, 3, 4, 4, 5));

Map<Integer, Integer> freq = new HashMap<>();
for (Iterator<Integer> it = list.iterator(); it.hasNext(); ) {
    if (freq.merge(it.next(), 1, Integer::sum) > 2) {
        it.remove();
    }
}
System.out.println(list); // -> [2, 2, 3, 4, 4, 5]

If the input is provided as an array, then a new resized array should be created and appropriate elements need to be copied.

int[] arr = {2, 2, 2, 3, 3, 4, 4, 2, 3, 5, 6, 4, 2};
Map<Integer, Integer> freq2 = new HashMap<>();

int i = 0;
for (int n : arr) {
    if (freq.merge(n, 1, Integer::sum) <= 2) {
        arr[i  ] = n;
    }
}
arr = Arrays.copyOf(arr, i);
System.out.println(Arrays.toString(arr)); // -> [2, 2, 3, 3, 4, 4, 5, 6]