samedi 2 juillet 2016

Function that returns kth smallest element


I'm trying to write a function that returns the kth smallest element in a vector. I have to do this iteratively and cannot sort the elements. Below is what I have so far but I either get a segmentation fault or an incorrect number from the vector. Any help would be much appreciated!

#include<vector>
#include<iostream>
using namespace std;

int iterative_kth_element(vector<int> &vec, size_t k){

   int cur = 0;
   int vecSmallestLocation = 0;
   for(int i=0; i<k; i++){
      if(vec.empty()){
         return cur;
      }
      cur = vec[0];
      for(int j=0; j<vec.size(); j++){
         if(vec[j]<cur){
            cur = vec[j];
            vecSmallestLocation = j;
         }
      }
      vec.erase(vec.begin()+(vecSmallestLocation));
   }

   cout << cur << endl;
   return cur;
}

int main(){
   vector<int> vec;
   vec.push_back(6);
   vec.push_back(21);
   vec.push_back(98);
   vec.push_back(14);
   vec.push_back(5);
   vec.push_back(7);
   vec.push_back(9);

   iterative_kth_element(vec, 3); // returns 6 but thats wrong
   //iterative_kth_element(vec, 4); // seg fault

}

Aucun commentaire:

Enregistrer un commentaire