Jul 6, 2022 · Jul 6, 2022
diff --git a/java/347-Top-K-Frequent-Elements.java b/java/347-Top-K-Frequent-Elements.java
 class Solution {
 class Solution1 {
    /**
     * Time Complexity: O(nlog(k))
     * Space Complexity: O(n)
     */
    public int[] topKFrequent(int[] nums, int k) {
        int[] arr = new int[k];
        HashMap<Integer, Integer> map = new HashMap<>();
        return arr;
    }
 }

 class Solution2 {
    /**
     * Time Complexity: O(n)
     * Space Complexity: O(n)
     */
    public int[] topKFrequent(int[] numbers, int k) {
 HashMap<Integer, Integer> map = new HashMap<>();
 for (int number : numbers)
 map.put(number, map.getOrDefault(number, 0) + 1);

 int size = map.size();
 int[] keys = new int[size];
 int i = 0;
 for (int key : map.keySet())
 keys[i++] = key;

 select(keys, map, 0, size - 1, size - k);
 return Arrays.copyOfRange(keys, size - k, size);
 }

    // Modified implementation of Hoare's selection algorithm:

 private void select(int[] keys, Map<Integer, Integer> map, int left, int right, int kSmallest) {
 while (left != right) {
 int pivot = partition(keys, map, left, right, (left + right) / 2);

 if (kSmallest == pivot) return;

 if (kSmallest < pivot) right = pivot - 1;
 else left = pivot + 1;
 }
 }

 private int partition(int[] keys, Map<Integer, Integer> map,int left, int right, int pivot) {
 int pivotValue = map.get(keys[pivot]);
 swap(keys, pivot, right);
 int index = left;

 for (int i = left; i <= right; i++)
 if (map.get(keys[i]) < pivotValue) {
 swap(keys, i, index);
 index++;
 }
 swap(keys, right, index);
 return index;
 }

    private void swap(int[] array, int i1, int i2) {
 int temp = array[i1];
 array[i1] = array[i2];
 array[i2] = temp;
 }
 }
Original file line number	Diff line number	Diff line change
		@@ -1,4 +1,8 @@
		class Solution {
		class Solution1 {
		/**
		* Time Complexity: O(nlog(k))
		* Space Complexity: O(n)
		*/
		public int[] topKFrequent(int[] nums, int k) {
		int[] arr = new int[k];
		HashMap<Integer, Integer> map = new HashMap<>();
Expand All		@@ -17,3 +21,57 @@ public int[] topKFrequent(int[] nums, int k) {
		return arr;
		}
		}

		class Solution2 {
		/**
		* Time Complexity: O(n)
		* Space Complexity: O(n)
		*/
		public int[] topKFrequent(int[] numbers, int k) {
		HashMap<Integer, Integer> map = new HashMap<>();
		for (int number : numbers)
		map.put(number, map.getOrDefault(number, 0) + 1);

		int size = map.size();
		int[] keys = new int[size];
		int i = 0;
		for (int key : map.keySet())
		keys[i++] = key;

		select(keys, map, 0, size - 1, size - k);
		return Arrays.copyOfRange(keys, size - k, size);
		}

		// Modified implementation of Hoare's selection algorithm:

		private void select(int[] keys, Map<Integer, Integer> map, int left, int right, int kSmallest) {
		while (left != right) {
		int pivot = partition(keys, map, left, right, (left + right) / 2);

		if (kSmallest == pivot) return;

		if (kSmallest < pivot) right = pivot - 1;
		else left = pivot + 1;
		}
		}

		private int partition(int[] keys, Map<Integer, Integer> map,int left, int right, int pivot) {
		int pivotValue = map.get(keys[pivot]);
		swap(keys, pivot, right);
		int index = left;

		for (int i = left; i <= right; i++)
		if (map.get(keys[i]) < pivotValue) {
		swap(keys, i, index);
		index++;
		}
		swap(keys, right, index);
		return index;
		}

		private void swap(int[] array, int i1, int i2) {
		int temp = array[i1];
		array[i1] = array[i2];
		array[i2] = temp;
		}
		}