I usually use something like this: (~. ,. #/.~) list 2 8 3 11 4 8 5 7 6 5 7 5 8 5 9 2 1 2 0 1
You can sort that if you prefer: /:~ (~. ,. #/.~) list 0 1 1 2 2 8 3 11 4 8 5 7 6 5 7 5 8 5 9 2 That said, when working with really large data sets, sometimes it makes more sense to sort the values and then look for where they change. L=: /:~ list b=: 1,2 ~:/\ L ... Thanks, -- Raul On Tue, Mar 31, 2015 at 12:10 PM, Jon Hough <[email protected]> wrote: > A fairly common technical question for programming interviews is to write (on > a whiteboard)a method to find how many duplicates of each number exist in a > list of numbers. > e.g. if list = 1 3 2 1 5 2 > then the answer would be 2 1's, 2 2's, one 3 and one 5. > The trick is to do it in a time efficient way. In a standard programming > language (Java, C++ etc),the naive approach is to do two passes and count how > many of each number are duplicated. This approach takes n(n-1)/2 comparisons, > so could be regarded as O(n^2).The better approach would be to create a > dictionary / hashtable for each number and add items to the correctslot (i.e. > key in the dictionary). > > But for J, it seems there is not a readily available fast approach to > this.e.g. > > list =: 2 3 4 3 2 3 4 5 6 5 4 7 8 9 7 6 4 6 2 1 2 3 4 3 2 3 4 5 7 5 2 3 5 8 9 > 0 4 3 2 3 1 2 6 5 7 8 7 8 3 4 5 3 6 8 > > > I want to count how many duplicates appear: > > > > > +/ ((i.10)&="_ 0)list > > > (result: 1 2 8 11 8 7 5 5 5 2) > > > > > > I think this is O(n^2), since it first constructs nxn table before folding +/. > > > My result is correct but my method is slooow. > Is there a better (faster, lower complexity) way to solve this? > > > Regards, > Jon > > > > > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
