Java Solution (16ms, beats 99.43%)


  • 0
    Q
    1. quick sort the array
    2. loop the array and put the frequency and value of each element into two separate & with each other synchronized arrays by using insert sort in frequency descending order till k
    public List<Integer> topKFrequent(int[] nums, int k) {
            if (nums == null || k <= 0) {
    			return null;
    		}
    		if (nums.length == 1) {
    			List<Integer> result = new ArrayList<>();
    			result.add(nums[0]);
    			return result;
    		} 
    		sort(nums, 0, nums.length - 1);
    		return getTopK(nums, k);
        }
    	
    // quick sort
    	private void sort(int[] nums, int i, int j) {
    		int left = i;
    		int right = j;
    		int mid = i + (j - i) / 2;
    		int midValue = nums[mid];
    		
    		if (i >= j) {
    			return;
    		}
    		
    		while (i < j) {
    			while (nums[i] < midValue) {
    				i++;
    			}
    			while (nums[j] > midValue) {
    				j--;
    			}
    			if (i <= j) {
    				int temp = nums[i];
    				nums[i] = nums[j];
    				nums[j] = temp;
    				i++;
    				j--;
    			}
    		}
    		sort(nums, left, j);
    		sort(nums, i, right);
    	}
    	// count the frequency on sorted array 
    	private List<Integer> getTopK(int[] nums, int k) {
    		List<Integer> valueResult = new ArrayList<>();
    		List<Integer> frequentResult = new ArrayList<>();
    		int i = 0;
    		int count = 1;
    		while (i < nums.length - 1) {
    			if (nums[i] == nums[i + 1]) {
    				count++;
    			} else {
    				insertOrder(frequentResult, count, valueResult, nums[i], k);
    				
    				count = 1;
    			}
    			i++;
    		}
    		insertOrder(frequentResult, count, valueResult, nums[i], k);
    			
    		return valueResult;
    	}
    	
    // insert sort the frequent array, with which the value array is kept synchronized
    	private void insertOrder(List<Integer> frequentResult, int currentFrequent, List<Integer> valueResult, int currentValue, int k) {
    		if (frequentResult.isEmpty()) {
    			frequentResult.add(currentFrequent);
    			valueResult.add(currentValue);
    		} else {
    			int insertIndex = getInsertIndex(frequentResult, currentFrequent);
    			
    			frequentResult.add(insertIndex, currentFrequent);
    			valueResult.add(insertIndex, currentValue);
    			if (frequentResult.size() > k) {
    				frequentResult.remove(k);
    				valueResult.remove(k);
    			}
    		} 
    	}
    	// get inserting point
    	private int getInsertIndex(List<Integer> frequentResult, int currentFrequent) {
    		int i = 0;
    		int j = frequentResult.size() - 1;
    		int m = i + (j - i) / 2;
    		while (i <= j) {
    			if (frequentResult.get(m) < currentFrequent) {
    				j = m - 1;
    			} else if (frequentResult.get(m) > currentFrequent) {
    				i = m + 1;
    			} else {
    				return m;
    			}
    			m = i + (j - i) / 2;
    		}
    		return i;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.