search

iluwatar / 30-seconds-of-java

Collection of reusable tested Java 17 compatible code snippets that you can understand in 30 seconds or less.
https://java-design-patterns.com/snippets.html
MIT License
1.04k stars 409 forks source link

Enhance the performance of ArrayMode #210

Closed XieGuochao closed 5 months ago

XieGuochao commented 5 months ago

Hi, I find there is much space to improve the performance of ArrayMode.

If the element is comparable, I propose the following algorithm:

  1. Sort the array.
  2. Do a single scan and get the mode(s).

The original complexity is O(N^2) while the new one is O(N log N) with O(1) space complexity.

Can you assign this to me and I will try to implement it?

XieGuochao commented 5 months ago

If we cannot modify the array, need O(N) additional space and this algorithm has no advantage.