Share my binary search solution


  • 0
    time: O(nlogn), space: O(n)
    public class Solution {
        public String[] findRelativeRanks(int[] nums) {
            int n = nums.length;
            String[] res = new String[n];
            int[] temp = new int[n];
            for(int i = 0; i < n; i++) {
                temp[i] = nums[i];
            }
            Arrays.sort(temp);
            for(int i = 0; i < n; i++) {
                int idx = binarySearch(nums[i], temp);
                if(idx == n - 1) {
                    res[i] = "Gold Medal";
                } else if(idx == n - 2) {
                    res[i] = "Silver Medal";
                } else if(idx == n - 3) {
                    res[i] = "Bronze Medal";
                } else {
                    res[i] = (n - idx) + "";
                }
            }
            return res;
        }
        
        private int binarySearch(int num, int[] temp) {
            int left = 0;
            int right = temp.length - 1;
            while(left <= right) {
                int mid = left + (right - left)/2;
                if(temp[mid] == num){
                    return mid;
                } else if(temp[mid] > num) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            return -1;
        }
    }

Log in to reply
 

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