Java very Easy and Short(15 lines Binary Search and Bucket Sort) solutions


  • 5
    K

    Bucket Sort Solution

    class Solution {
        public int smallestDistancePair(int[] nums, int k) {
            int len=nums.length;
            int len2=1000000;
            int[] dp= new int[len2];
            for(int i=1;i<len;i++){
                for(int j=0;j<i;j++){
                 int dif= Math.abs(nums[i]-nums[j]);
                   dp[dif]++;
                }
            }
            int sum=0;
            for(int i=0;i<len2;i++){
                sum+=dp[i];
                if(sum>=k) return i;
            }
            return 0;
        }
         }
    
    

    Following is the Binary Search Solution:

    class Solution {
        public int smallestDistancePair(int[] nums, int k) {
            Arrays.sort(nums);
            int n = nums.length, low = 0, hi = nums[n-1] - nums[0];
            while (low < hi) {
                int cnt = 0, j = 0, mid = (low + hi)/2;
                for (int i = 0; i < n; ++i) {
                    while (j < n && nums[j] - nums[i] <= mid) ++j;
                    cnt += j - i-1;
                }
                if (cnt >= k) 
                    hi = mid;
                
                else low = mid + 1;
            }
            
            return low;
        }
    }
    

  • 0
    F

    Feeling your code is very time-consuming.


Log in to reply
 

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