educative.io

K Closest Numbers - Solution without binary sort

Courses
,
#1

Is this a viable alternative to the K Closest number problem? It is a lot more simple, and I dont think it really affects run time, at least in the worst case.


const find_closest_elements = function (arr, K, X) {
  const maxHeap = new Heap([], null, ((a, b) => a[0] - b[0]));

  for (let i = 0; i < arr.length; i++) {
    maxHeap.push([Math.abs(X - arr[i]), arr[i]]);
  
    if (maxHeap.length > K)
      maxHeap.pop();
  }

  let result = [];
  let maxHeapLength = maxHeap.length;
  for (let i = 0; i < maxHeapLength; i++){
    result.push(maxHeap.pop()[1]);
  }

  return result;
};


console.log(`'K' closest numbers to 'X' are: ${find_closest_elements([5, 6, 7, 8, 9], 3, 7)}`)
console.log(`'K' closest numbers to 'X' are: ${find_closest_elements([2, 4, 5, 6, 9], 3, 6)}`)
console.log(`'K' closest numbers to 'X' are: ${find_closest_elements([2, 4, 5, 6, 9], 3, 10)}`)
#2

Thisis the solution with b_search removing the logN piece

using namespace std;

#include
#include
#include
#include
#include

class KClosestElements {
public:
struct numCompare {
bool operator()(const pair<int, int> &x, const pair<int, int> &y) {
return (x.second == y.second) ? (x.first > y.first) : (x.second < y.second) ; }
};

static int diff(int a, int base){
return abs(a - base);
}

static vector findClosestElements(const vector &arr, int K, int X) {
vector result;
priority_queue< pair<int,int>, vector<pair<int,int>>, numCompare> maxHeap;

for(int num: arr){
  if(maxHeap.size() < K){
    maxHeap.push({num, diff(num,X)});
  } else{
    if(diff(num,X) < maxHeap.top().second){
      maxHeap.push({num, diff(num,X)});
      maxHeap.pop();
    }
  }
}

while(!maxHeap.empty()){
  result.push_back(maxHeap.top().first);
  maxHeap.pop();
}
sort(result.begin(),result.end());
return result;

}
};

int main(int argc, char *argv[]) {
vector result = KClosestElements::findClosestElements(vector{5, 6, 7, 8, 9}, 3, 7);
cout << "‘K’ closest numbers to ‘X’ are: ";
for (auto num : result) {
cout << num << " ";
}
cout << endl;

result = KClosestElements::findClosestElements(vector{2, 4, 5, 6, 9}, 3, 6);
cout << "‘K’ closest numbers to ‘X’ are: ";
for (auto num : result) {
cout << num << " ";
}
cout << endl;
}