I was attempting to solve 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 the map.

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

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

CodePudding user response：

In case if the order of the elements should be preserved, then it would be correct to use List.remove() because this method removes the very first occurrence of the given element. Also, removal of elements from a List has the worst case time complexity O(n), which leads to overall quadratic timecomplexity O(n^2). We can do better.

Instead, you can build and a new List while iterating over the given array. And simultaneously, you need to track the occurrences of the previously encountered element via a HashMap. If the number of occurrences of a current element hasn't exceeded the limit, it should be added to the resulting list, otherwise ignored.

Note: that this solution would run in O(n), since we're iterating the list twice: to generate the list. And then to turn it into an array, all the action needs to be performed during iterations run in O(1).

That's how it might be implemented:

public static int[] removeOccurrencesAboveLimit(int[] arr, int limit) {
    Map<Integer, Integer> occurrences = new HashMap<>();
    
    List<Integer> result = new ArrayList<>();
    for (int next : arr) {
        int freq = occurrences.merge(next,  1, Integer::sum); // returns a new Value (i.e. updated number of occurrences of the current array element)
        if (freq <= limit) result.add(next);
    }
    return toArray(result);
}

public static int[] toArray(List<Integer> list) {
    return list.stream().mapToInt(i -> i).toArray();
}

main()

public static void main(String[] args) {
    int[] arr = {3, 1, 2, 1, 3, 3, 4, 4, 5, 1, 3, 5};

    System.out.println(Arrays.toString(removeOccurrencesAboveLimit(arr, 2)));
}

Output:

[3, 1, 2, 1, 3, 4, 4, 5, 5]

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：

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]

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);

By the way you can solve your problem better.

List<Integer> list = new ArrayList<>(Arrays.asList(2, 2, 2, 3, 4, 4, 5));
Map<Integer,Long> resultMap=  list.stream()
    .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

resultMap.entrySet()
        .stream()
        .forEach(entry -> {
            if(entry.getValue() > 2){
                list.remove(entry.getKey());
            }
        });
        
 System.out.println(list.toString());