Find the kth smallest number obtained by subtracting two element in sorted array-CodePudding

I have a sorted array with length n where 1e5<= n >1, how can i find the kth smallest number obtained by substracting from two elements in the array . For example, i have array {1,4,9,16} and k equal 5, then i have {3,5,7,8,12,15} and the result is 12 , i couldn,t find find any solution other than finding all result of subtracting two element , this algorism will take O(n^2)

CodePudding user response：

This is more of a math trick then computing. But the order of differences comes from range between 2 consecutive numbers (first the diff is 1 distance, then we try 2 distance etc). See the output how it correlates to the delta of distances.

var arr = [1, 4, 9, 16, 18]
var diff = [3, 5, 7, 2]
var diff2 = [8, 12, 9]
var diff3 = [15, 14]
var diff4 = [17]


console.log(kth(arr, 1));
console.log(kth(arr, 2));
console.log(kth(arr, 3));
console.log(kth(arr, 4));
console.log(kth(arr, 5));
console.log(kth(arr, 6));
console.log(kth(arr, 7));
console.log(kth(arr, 8));
console.log(kth(arr, 9));
console.log(kth(arr, 10));

function kth(arr, k) {
  var len = arr.length - 1;
  var delta = 1;
  while (len < k && len > 0) {
    delta  = 1
    k -= len;
    len--;
  }
  var diff = []
  for (var i = delta; i < arr.length; i  ) {
    diff.push(arr[i] - arr[i - delta]);
  }
  diff.sort(function(a, b) {
    return  a -  b;
  });
  return diff[k-1]
}

CodePudding user response：

I look at this problem like this.

For [a,b,c,d] such a<b<c<d and x,y,z>0 and b = a x, c = b y, d=c z, then b-a = x, c-b = y, c-a = x y, d-b = y z, d-a = x y z. What does it tell us? The more apart are the elements the bigger the difference, and it adds up with every step.

It is unknown if x<y or x>y but for sure x y>x and x y>y, so your differences can be divided into distance classes.

diff_1 = {d-c,c-b,b-a}, diff_2 = {d-b,c-a}, diff_3={d-a}

now what you probably can see by now is min(diff_1) < min(diff_2) < min(diff_3), so to find the second smallest difference you don't need to check for min(diff_3) because it is at best the third smallest element.

So what you do is to implement something like this pseudocode:

int findLeastDiff<k>(std::vector<int> v)
{
  assert(v_contains_k_distinct_elements(v));
  std::vector<int> result;
  std::sort(v.begin(),v.end()); // O(nlog(n));
  v.erase(std::unique(v.begin(),v.end()),v.end()); // O(n)
  for<<int i=1; i<=k;   i>>
  {
     adjacent_difference<i>(v.begin(), v.end(), std::back_inserter(result));// O(n-i)
  } // O(k(n-k/2)) = O(k*n)
  std::sort(result.begin(), result.begin());  // O(nlog(n));
  result.erase(std::unique(result.begin(),result.end()),result.end()); // O(n)
  return result[k];
}

The above is just a concept and for sure can be optimized a lot. What is the complexity? O(nlog(n) n k*n nlog(n) n) = O((2log(n) k 2)*n)

It probably can be optimized with some clever way of reducing the search space by removing ranges with already too big differances.

CodePudding user response：

Kth Smallest Element in multiple sorted arrays shows how to efficiently find the kth smallest element in an array of sorted arrays.

For this case you do not want to construct the actual sorted arrays. Just take the original array and say at which index the larger number is. This will make for some tricky indexing.

The total runtime on average will be O(n log(n)). The worst case is O(n log(n)^2).