CppMedian

main.cpp

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int GetMedianOfTwoSortedVector(vector<int>& arr1, vector<int>& arr2);

int main() 
{
  vector<int> v1 = {1, 3, 5}, v2 = {6, 7};
  
  cout << GetMedianOfTwoSortedVector(v1,v2) << endl;
  
  return 0;
}

int GetMedianOfTwoSortedVector(vector<int>& arr1, vector<int>& arr2)
{
  //배열이 정렬되어있다고 가정할 경우, 두 값을 비교하며 낮은 쪽의 인덱스를 올려주면 배열을 따로 합쳐 정렬하지 않아도 오름차순이 보장된다
  //마지막 중앙값 구하는 단계에서 마지막 선택한 인덱스를 알기 위해 bool 변수를 이용하여 기록한다.
  bool isArr1Index = false;
  int arr1Index = 0, arr2Index = 0;
  
  // 전체 사이즈가 짝수일 경우 두 값의 평균을 구하기 위해 변수화
  int sumOfArrSize = arr1.size()+arr2.size();
  // 두 벡터의 크기를 더한 뒤 반으로 나누어 중간 인자의 위치를 구함,
  int midIndex = (int)floor(sumOfArrSize / 2.f);
  
  //중앙값 인덱스(내림)까지 순회하며 오름차순으로 각 배열의 인덱스 순회
  for(int i=0;i<midIndex;i++)
  {
    if(arr1[arr1Index]<arr2[arr2Index])
    {
      arr1Index++;
      isArr1Index=true;
    }
    else
    {
      arr2Index++;
      isArr1Index=false;
    }
  }
  
  //두 배열의 길이의 합이 홀수일 경우 (중앙값이 하나일 경우)
  if(sumOfArrSize%2!=0)
  {
      return isArr1Index?arr1[arr1Index]:arr2[arr2Index];
  }
  else
  {
    int lowerMedian = isArr1Index?arr1[arr1Index]:arr2[arr2Index];
    int higherMedian = arr1[arr1Index]<arr2[arr2Index]?arr1[++arr1Index]:arr2[++arr2Index];
    
    return (lowerMedian+higherMedian)/2;
  }
}

cpp로 오름차순으로 정렬된 두 vector의 중앙값을 찾는 코드입니다. 문제풀이가 아직 능숙하지 않으므로 혹시라도 살펴보시고 개선사항이나 엣지케이스가 있다면 의견 남겨주시면 감사하겠습니다.

https://leetcode.com/problems/median-of-two-sorted-arrays/submissions/
해당 저지페이지에서 범위 초과 문제, 잘못된 값 도출 발견하여 수정 중입니다 :(