trjhtr

I wanted to remove the occurrence of an element from an array if it occurs more than n times. For example:

 20, 37, 20, 21 (n->1) -> 20, 37, 21
 1, 1, 1, 1, 1 (n->5) -> 1, 1, 1, 1, 1 
 1, 2, 3, 1, 1, 2, 1, 2, 3, 3, 2, 4, 5, 3, 1 (n->3 ) -> 1, 2, 3, 1, 1, 2, 2, 3, 3, 4, 5 

I tried the following code in java:

public class arr
 public static void main(String args)
 int a = 1,1,3,3,7,2,2,2,2; //Array of the elements
 int b =3; // maximum occurrences
 int u=1; // Counter for same number of elements
 int c = new int[nterms(a, b)]; //initializing new array
 int k=0; 
 int l=0;
 for(int i =a.length-1; i>=0; i--)
 k=0;
 // Checking the duplicate elements.
 for(int j=i-1; j>=0; j--)
 if(a[i]==a[j])
 k++; 
 
 
 if(k!=b) 
 c[c.length-u] = a[i];
 u++;
 
 
 for(int i =0; i<c.length; i++)
 System.out.println(c[i]); 
 

 // Returns no. of unique elements.
 public static int nterms(int x, int y)
 int k=0;
 int l=0;
 for(int i =0; i<x.length; i++)
 k=0;
 for(int j=i+1; j<x.length; j++)
 if(x[i]==x[j])
 k++; 
 
 
 if(k==y)
 l++;
 
 
 return (x.length-l);
 

It works fine but can anybody recommend a more short & efficient way.

Ok so I'll start with general stuff and then I'll talk about your particular problem:

• Commenting should explicit what the code don't already tell. If your comments tells what the code do it's probably a bad comment. Comment should be used to explain why you need this particular piece of code. See this excellent review for more examples. I am aiming the comment like Array of the elements, //initializing new array and the like here.


• 
  

  Naming stuff: you really shouldn't use non descriptive names. It's super hard to understand what they stand for, and you felt the need to comment.
  Why write

  
  
  

  int b =3; // maximum occurrences
  

  
  
  

  when you could have written

  
  
  

  int maximumOccurrence = 3;
  

  
  
  

  The name might be better, maybe maximumNumberOccurence, maximumNbrOccurence or something, but the point is, if you name your variable with name so obscure you need to comment them to explain, change the name and remove the comment, it's way easier to read the program that way

  
  



• Same for the method nterms you comment above that it Returns no. of unique elements so maybe the method should be named getNumberUniqueItem or a shorter name but more descriptive than nterms?

So that was for the generalities, now for your particular problem.

If I understand your algorithm, you go through your list of item, and then you count how many instance of this particular item exist in the list. It's a way to do it but it's not efficient because you need to go through your list as many times as there are items in your list.

Instead if you could keep count of items already encountered and added a score to each of them, you could go through the list only once. And if the operations for writing/reading the score of each item are fast, it's way faster than your method.

That's where you can use Map to insert and retrieve score.

Another point, you could use a method to declutter the main method.

So your problem could be solved with something like (pseudo Java, I did not try to compile nor run it)

 List<Integer> solve(int data, int limitNumberOccurence)
 
 Map itemNumberOccurence = new HashMap();
 List result = new ArrayList<Integer> ();

 foreach(int item : data)
 
 Integer itemInteger = new Integer(item);
 if(itemNumberOccurence.containsKey(itemInteger))
 
 Integer oldValue = itemNumberOccurence.get(itemInteger);
 itemNumberOccurence.put(itemInteger, oldvalue + 1));
 
 else
 
 itemNumberOccurence.put(itemInteger, new Integer(1));
 

 if(itemNumberOccurence.get(itemInteger).intValue() <= limitNumberOccurence)
 
 result.add(item);
 
 

 return result;
 

This method counts the number of occurrence of each item as the loop go through the array, and put allowed element into the list.

It's done in one pass, and put and get are efficient operation so it's good! The only bad point is that I add to the end of the result list I'm constructing, it's not too bad here because it's an ArrayList, but with other implementations/other languages you might want to prepend and reverse afterward for better performance. (I believe it's the case, maybe someone will correct me on this).

That's all I had to say, ask me questions if I was not clear enough, I hope you didn't find my review harsh, I just tried to tell you about everything I could see.

It's been said multiple times but you should avoid one letter variable most of the time.

Class name arr is also no good. It's recommended that class name follows camel case convention and using abbreviation is often considered bad.

Don't code something in your main as it makes it harder to test your code.

Putting it in an outside function makes for a clearer code :

public static int removeOccurencesFromArray(final int array, final long maxOccurence) 
 // TODO

Array have an "old-school" feel and I'd avoid them if possible. Consider using List (and especially ArrayList) for those kind of use case, thus transforming previous method in :

public static List<Integer> removeOccurencesFromList(final List<Integer> list, final long maxOccurence) 
 // TODO

Now, onto the main course :

I find your algorithm overly complex. :/

It's also higly "procedural" IMO, in modern computing we'd rather "tell" the program to do something instead of manipulating everything by ourselves.

Julien Rousé has shown a nice and short solution in another answer... which is probably faster than mine but please bear with me :)

(After rereading my answer, I see that I used some Java 8 tricks that may feel overwhelming if you are a beginner, if you are new to programming I'd recommend to not consider my solution)

Let's try to solve your problem step by step :

Here is a simple solution I came up with (almost the same as Julien Rousé)

1) count the number of occurences within your array... you end up with a structure linking all elements with the number of occurence... it's usually called a bag, while there are some java library that supports this structure let's keep things simple and use a Map

2) if any occurences count is greater than the maxOccurence parameter then it should be set to maxOccurence

3) for each elements in your array, print it if the number of occurences is greater than 0 and reduce the number of elements in your bag

Let's dig a bit in java 8... surely there's a tool for us in there.

We are looking for something that'd allow us to "tell" instead of creating everything by hand.

In the Collectors util class (https://docs.oracle.com/javase/8/docs/api/java/util/stream/Collectors.html), we can find some really fancy tools. For our use case, groupingBy and counting sounds useful.

groupingBy allows you to transform a stream of data into a map where the key is found using the first parameter.
counting counts the number of input elements (from Javadoc).

list.stream().collect(Collectors.groupingBy(element -> element, Collectors.counting()));

With this simple line, we now have the number of occurence of each elements of your list.

This is still not enough as we want to consider the maximum number of occurences.

We want to have the number of occurence if it's below a threshold.

Collectors (again) comes to the rescue :

list.stream().collect(Collectors.groupingBy(element -> element,
 Collectors.collectingAndThen(Collectors.counting(), v -> Math.min(v, maxOccurence))));

So we are counting unless we have more than maxOccurence, in which case the min will always give us maxOccurence as a result.
That's not very palatable though IMO, I'll use static import to make it cleaner. Let's also not forget to store the result.

 Map<Integer, Long> value = list.stream().collect(groupingBy(element -> element,
 collectingAndThen(counting(), v -> Math.min(v, maxOccurence))));

We can now easily compute the result :

 List<Integer> result = new ArrayList<>();
 for (Integer element : list) 
 long remaining = value.get(element);
 if (remaining > 0) 
 value.put(element, remaining - 1);
 result.add(element);
 
 

 return result;

If you really want to have an array at the end, use the toArray method ;)