1- class Solution {
1+ class Solution1 {
2+ /**
3+ * Time Complexity: O(nlog(k))
4+ * Space Complexity: O(n)
5+ */
26public int []topKFrequent (int []nums ,int k ) {
37int []arr =new int [k ];
48HashMap <Integer ,Integer >map =new HashMap <>();
@@ -17,3 +21,57 @@ public int[] topKFrequent(int[] nums, int k) {
1721return arr ;
1822 }
1923}
24+
25+ class Solution2 {
26+ /**
27+ * Time Complexity: O(n)
28+ * Space Complexity: O(n)
29+ */
30+ public int []topKFrequent (int []numbers ,int k ) {
31+ HashMap <Integer ,Integer >map =new HashMap <>();
32+ for (int number :numbers )
33+ map .put (number ,map .getOrDefault (number ,0 ) +1 );
34+
35+ int size =map .size ();
36+ int []keys =new int [size ];
37+ int i =0 ;
38+ for (int key :map .keySet ())
39+ keys [i ++] =key ;
40+
41+ select (keys ,map ,0 ,size -1 ,size -k );
42+ return Arrays .copyOfRange (keys ,size -k ,size );
43+ }
44+
45+ // Modified implementation of Hoare's selection algorithm:
46+
47+ private void select (int []keys ,Map <Integer ,Integer >map ,int left ,int right ,int kSmallest ) {
48+ while (left !=right ) {
49+ int pivot =partition (keys ,map ,left ,right , (left +right ) /2 );
50+
51+ if (kSmallest ==pivot )return ;
52+
53+ if (kSmallest <pivot )right =pivot -1 ;
54+ else left =pivot +1 ;
55+ }
56+ }
57+
58+ private int partition (int []keys ,Map <Integer ,Integer >map ,int left ,int right ,int pivot ) {
59+ int pivotValue =map .get (keys [pivot ]);
60+ swap (keys ,pivot ,right );
61+ int index =left ;
62+
63+ for (int i =left ;i <=right ;i ++)
64+ if (map .get (keys [i ]) <pivotValue ) {
65+ swap (keys ,i ,index );
66+ index ++;
67+ }
68+ swap (keys ,right ,index );
69+ return index ;
70+ }
71+
72+ private void swap (int []array ,int i1 ,int i2 ) {
73+ int temp =array [i1 ];
74+ array [i1 ] =array [i2 ];
75+ array [i2 ] =temp ;
76+ }
77+ }