Advertisement
framp

Find K-smallest elements in a N-array

Jun 8th, 2014
193
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //Given an array of N elements find the K biggest elements and the K smallest elements
  2.  
  3. function lol(N, K){
  4.   var array = [];
  5.   for (var i=0; i<N; i++){
  6.     array[i] = Math.random()*1000>>0
  7.   }
  8.   console.log(array);
  9.   var sorted = array.slice().sort(function(a,b){return a-b});
  10.   console.log(sorted);
  11.  
  12.   var result = {
  13.     '>=': {
  14.       array: [],
  15.       indexes: []
  16.     },
  17.     '<=': {
  18.       array: [],
  19.       indexes: []
  20.     }
  21.   };
  22.    
  23.   for (var i=0; i<array.length; i++){
  24.     var element = array[i];
  25.     for (var l in result){
  26.       var inserted = false;
  27.       var sortedArray = result[l].array;
  28.       var indexesArray = result[l].indexes;
  29.       for (var j=0; j<sortedArray.length; j++){
  30.         if (condition(l, sortedArray[j], element) && !inserted){
  31.           sortedArray.splice(j, 0, element);
  32.           indexesArray.splice(j, 0, i);
  33.           j++;
  34.           inserted = true;
  35.         }
  36.       }
  37.       if (!inserted){
  38.         sortedArray.push(element);
  39.         indexesArray.push(i);
  40.       }
  41.       if (sortedArray.length>K)
  42.         while(sortedArray.length!==K){
  43.           sortedArray.pop();
  44.           indexesArray.pop();
  45.         }
  46.     }
  47.   }
  48.   var min = sorted.slice(0, K);
  49.   var max = sorted.slice(Math.max(sorted.length - K, 1));
  50.   max.sort(function(a,b){return b-a})
  51.  
  52.   console.log('MIN', result['>='].array, result['>='].indexes, result['>='].array.join('')===min.join(''));
  53.   console.log('MAX', result['<='].array, result['<='].indexes, result['<='].array.join('')===max.join(''));
  54. }
  55. function condition(condition, a, b){
  56.   if (condition==='>=')
  57.     return a>=b;
  58.   if (condition==='<=')
  59.     return a<=b;
  60.   if (condition==='>')
  61.     return a>b;
  62.   if (condition==='<')
  63.     return a<b;
  64. }
  65.  
  66. lol(10, 5);
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement