java - Determining the element that occurred the most in O(n) time and O(1) space -

let me start off saying not homework question. trying design cache eviction policy depends on entries occurred in cache. in software terms, assume have array different elements , want find element occurred most. example: {1,2,2,5,7,3,2,3} should return 2. since working hardware, naive o(n^2) solution require tremendous hardware overhead. smarter solution of using hash table works software because hash table size can change in hardware, have fixed size hash table, not big, collisions lead wrong decisions. question is, in software, can solve above problem in o(n) time complexity , o(1) space?

there can't o(n) time, o(1) space solution, @ least not generic case.

as amit points out, solving this, find solution element distinctness problem (determining whether elements of list distinct), has been proven take Θ(n log n) time when not using elements index computer's memory. if use elements index computer's memory, given unbounded range of values, requires @ least Θ(n) space. given reduction of problem one, bounds problem enforces identical bounds on problem.

however, practically speaking, range bounded, if no other reason type 1 typically uses store each element in has fixed size (e.g. 32-bit integer). if case, allow o(n) time, o(1) space solution, albeit possibly slow , using space due large constant factors involved (as time , space complexity depend on range of values).

2 options:

• counting sort

  keeping array of number of occurrences of each element (the array index being element), outputting frequent.

  if have bounded range of values, approach o(1) space (and o(n) time). technically hash table approach, constant factors here presumably large acceptable.

  related options radix sort (has in-place variant, similar quicksort) , bucket sort.

• quicksort

  repeatedly partitioning data based on selected pivot (through swapping) , recursing on partitions.

  after sorting can iterate through array, keeping track of maximum number of consecutive elements.

  this take o(n log n) time , o(1) space.