fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdint>
  4. #include <climits>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. int kthSmallestMine(vector<vector<int>>& matrix, int k) {
  9.     int lowest=INT_MAX, highest=INT_MIN;
  10.     for(vector<int> row: matrix) {
  11.         lowest=min(lowest, row[0]);
  12.         highest=max(highest, row[row.size()-1]);
  13.     }
  14.  
  15.     while(lowest<highest) {
  16.         int mid=lowest+(highest-lowest+1)/2;
  17.         int places=0;
  18.  
  19.         for(int i=0; i<matrix.size(); i++) {
  20.             places+=(upper_bound(matrix[i].begin(), matrix[i].end(), mid)-matrix[i].begin());
  21.         }
  22.         if(places<=k) lowest=mid;      //this gives a number _not_ in the matrix (14)
  23.         else highest=mid-1;
  24.         // if(places<k) lowest=mid+1;  //this gives a number _in_ the matrix (13)
  25.         // else highest=mid;   //also use mid=lowest+(highest-lowest)/2 instead;
  26.     }
  27.  
  28.     return lowest;
  29. }
  30.  
  31. int kthSmallestTheirs(vector<vector<int>>& matrix, int k) {
  32.     int lowest=INT_MAX, highest=INT_MIN;
  33.     for(vector<int> row: matrix) {
  34.         lowest=min(lowest, row[0]);
  35.         highest=max(highest, row[row.size()-1]);
  36.     }
  37.  
  38.     while(lowest<highest) {
  39.         int mid=lowest+(highest-lowest)/2;
  40.         int places=0;
  41.  
  42.         for(int i=0; i<matrix.size(); i++) {
  43.             places+=(upper_bound(matrix[i].begin(), matrix[i].end(), mid)-matrix[i].begin());
  44.         }
  45.         if(places<k) lowest=mid+1;  //this gives a number _in_ the matrix (13)
  46.         else highest=mid;   //also use mid=lowest+(highest-lowest)/2 instead;
  47.     }
  48.  
  49.     return lowest;
  50. }   
  51. int main() {
  52. 	vector<vector<int>> v={{1,100,1000}, {10, 150, 1500}, {30, 300, 3000}};
  53. 	cout<<kthSmallestMine(v, 7)<<"\n";
  54. 	cout<<kthSmallestTheirs(v, 7);
  55.  
  56. 	return 0;
  57. }
Success #stdin #stdout 0.01s 5588KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1499
1000
https://ideone.com/2SCgYf
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!