はじめに

---

vector<int>& nums1・vector<int>& nums2が与えられ、それらの要素全ての中央値を返す問題

コード全体

---

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
  vector<int> nums;
  nums.reserve(nums1.size() + nums2.size());
  size_t i=0, j=0;
  while( i<nums1.size() && j<nums2.size() ){
    if( nums1[i] < nums2[j] ) nums.push_back(nums1[i++]);
    else nums.push_back(nums2[j++]);
  }
  while( i<nums1.size() ) nums.push_back(nums1[i++]);
  while( j<nums2.size() ) nums.push_back(nums2[j++]);
  if(nums.size() % 2) return nums[nums.size()/2];
  else return ( nums[nums.size()/2] + nums[nums.size()/2-1] ) /2.0;
  return 0;
}

解説

---

nunsは、入力配列を結合した配列を格納する。要素数は予めわかっているため、std::vector::reverse()でメモリを確保した。

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
  vector<int> nums;
  nums.reserve(nums1.size() + nums2.size());

nums1・nums2それぞれの先頭から順に、小さい方をnumsの末尾に足していく。 １つ目のwhile-loopは、比較しながら末尾に足しており、比較する数が無くなったらループから抜ける。 ２、３つ目のwhile-loopは、残った数を末尾に足していく。

  size_t i=0, j=0;
  while( i<nums1.size() && j<nums2.size() ){
    if( nums1[i] < nums2[j] ) nums.push_back(nums1[i++]);
    else nums.push_back(nums2[j++]);
  }
  while( i<nums1.size() ) nums.push_back(nums1[i++]);
  while( j<nums2.size() ) nums.push_back(nums2[j++]);

要素が奇数個の場合は真ん中の数を、偶数個の場合は真ん中二つの平均値を返す。

  if(nums.size() % 2) return nums[nums.size()/2];
  else return ( nums[nums.size()/2] + nums[nums.size()/2-1] ) /2.0;
  return 0;
}