Find the median in two sorted array -- Amazon

Solution

#include <iostream>

#include <string>

#include <algorithm>

#include <vector>

#include <iomanip>

#include <cstdlib>

#include <cassert>

using namespace std;

const int MAX_VALUE = 30;

const int MAX_SIZE = 20;

void InitArray(vector<int>& vec, int size)

{

for(int i = 0; i < size; ++i){

vec.push_back(rand() % MAX_VALUE);

}

sort(vec.begin(), vec.end());

}

void Display(vector<int>& vec, string str)

{

cout << str << ": " << " -- len(" << vec.size() <<")" << endl;

copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, " "));

cout << endl;

}

int FindMedian(vector<int>& vec1, vector<int>& vec2)

{

assert(vec1.size() + vec2.size() != 0);

if(vec1.size() == 0){

return vec2.at(vec2.size() / 2);

}

else if(vec2.size() == 0){

return vec1.at(vec1.size() / 2);

}

int len = vec1.size() + vec2.size();

int med = len / 2;

int index = -1;

int index1 = 0;

int index2 = 0;

int ml, mr;

while(index < med && index1 < vec1.size() && index2 < vec2.size()){

index ++;

if(vec1.at(index1) < vec2.at(index2)){

ml = vec1.at(index1);

index1 ++;

}

else{

ml = vec2.at(index2);

index2 ++;

}

}

if(index == med){

return ml;

}

else if(index1 == vec1.size()){

return vec2.at(med - vec1.size());

}

else{ // index2 == vec2.size()

return vec1.at(med - vec2.size());

}

}

int main(int argc, char* argv[])

{

srand(1);

for(int i = 1; i < 10; ++i){

int size1 = rand() % MAX_SIZE;

int size2 = rand() % MAX_SIZE;

vector<int> vec1, vec2;

InitArray(vec1, i);

Display(vec1, "Array 1");

InitArray(vec2, size2);

Display(vec2, "Array 2");

vector<int> vec3(vec1);

copy(vec2.begin(),vec2.end(),back_inserter(vec3));

sort(vec3.begin(), vec3.end());

copy(vec3.begin(), vec3.end(), ostream_iterator<int>(cout, " "));

cout << endl;

cout << "The median in two arrays are ";

cout << FindMedian(vec2, vec1) << endl << endl;

}

return 0;

}

Output

Array 1: -- len(1)

4

Array 2: -- len(7)

4 10 14 18 18 22 29

4 4 10 14 18 18 22 29

The median in two arrays are 18

Array 1: -- len(2)

1 27

Array 2: -- len(5)

1 2 11 25 27

1 1 2 11 25 27 27

The median in two arrays are 11

Array 1: -- len(3)

2 3 24

Array 2: -- len(11)

5 6 8 9 11 17 18 21 22 22 26

2 3 5 6 8 9 11 17 18 21 22 22 24 26

The median in two arrays are 17

Array 1: -- len(4)

19 23 24 25

Array 2: -- len(7)

1 2 3 3 14 21 21

1 2 3 3 14 19 21 21 23 24 25

The median in two arrays are 19

Array 1: -- len(5)

14 17 22 27 27

Array 2: -- len(8)

5 16 19 19 20 21 23 28

5 14 16 17 19 19 20 21 22 23 27 27 28

The median in two arrays are 20

Array 1: -- len(6)

2 4 10 16 26 28

Array 2: -- len(8)

3 6 9 10 15 20 20 21

2 3 4 6 9 10 10 15 16 20 20 21 26 28

The median in two arrays are 15

Array 1: -- len(7)

4 6 16 20 23 24 26

Array 2: -- len(9)

8 9 11 13 17 24 26 28 28

4 6 8 9 11 13 16 17 20 23 24 24 26 26 28 28

The median in two arrays are 20

Array 1: -- len(8)

0 3 5 11 18 19 24 27

Array 2: -- len(9)

0 5 6 9 11 14 22 23 26

0 0 3 5 5 6 9 11 11 14 18 19 22 23 24 26 27

The median in two arrays are 11

Array 1: -- len(9)

0 5 6 11 12 15 16 17 27

Array 2: -- len(13)

4 4 7 10 10 11 11 16 20 21 22 27 27

0 4 4 5 6 7 10 10 11 11 11 12 15 16 16 17 20 21 22 27 27 27

The median in two arrays are 12

Press any key to continue . . .