C++의 행별 정렬 행렬에서 중앙값 찾기

이 문제에서는 요소가 행별로 정렬된 2D 배열 mat[r][c]가 제공됩니다. 우리의 임무는 행별로 정렬된 행렬에서 중앙값을 찾는 것입니다.

설명 − 행렬 요소의 중앙값을 찾아야 합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

mat = {
   {2, 4, 7},
   {5, 6, 8},
   {4, 8, 9}
}

출력

6

설명

배열에 저장된 행렬의 요소는 &minus

{2, 4, 4, 5, 6, 7, 8, 8, 9}
The median is 6.

솔루션 접근 방식

문제에 대한 간단한 해결책은 배열의 모든 요소를 ​​저장하는 것입니다. 그런 다음 배열을 정렬하여 중앙값 요소를 찾습니다.

문제에 대한 보다 효과적인 솔루션은 is가 행렬에서 정확히 (r*c)/2개의 더 작은 요소를 갖는다는 사실을 사용하여 중앙값 요소를 찾는 것입니다. 그리고 우리는 이 조건을 따르는 배열의 요소를 찾을 것입니다. 이를 위해 행렬의 가장 작은 요소와 가장 큰 요소를 취하는 행렬에 대한 이진 검색을 사용하고 범위의 중간을 찾고 작은 요소의 수를 확인합니다. r*c/2와 같으면 숫자를 반환합니다. (r*c)/2보다 크면 가장 큰 요소를 발견된 중간보다 작은 요소로 변경하고 개수가 (r*c)/2보다 작으면 가장 작은 요소에 대해서도 동일한 작업을 수행합니다.

중간 요소보다 작은 요소의 수는 중간보다 큰 첫 번째 요소의 인덱스를 찾음으로써 모든 요소를 ​​행 단위로 계산하거나 단순히 C++의 내장 함수인 upper_bound를 사용할 수 있습니다.

우리 솔루션의 작동을 설명하는 프로그램

예시

#include<bits/stdc++.h>
using namespace std;
#define c 3
#define r 3
int findMedian(int mat[][c]) {
   int smallest = INT_MAX, largest = INT_MIN;
   for (int i=0; i<r; i++) {
      if (mat[i][0] < smallest)
         smallest = mat[i][0];
      if (mat[i][c-1] > largest)
         largest = mat[i][c-1];
   }
   while (smallest < largest){
      int mid = smallest + (largest - smallest) / 2;
      int smallCount = 0;
      for (int i = 0; i < r; ++i)
         smallCount += upper_bound(mat[i], mat[i]+c, mid) -
      mat[i];
      if (smallCount < ( (r * c + 1) / 2 ))
         smallest = mid + 1;
      else
         largest = mid;
   }
   return smallest;
}
int main(){
   int mat[][c]= { {2, 5, 7}, {4, 6, 8}, {1, 8, 9} };
   cout<<"The median of the matrix is "<<findMedian(mat);
   return 0;
}

출력

The median of the matrix is 6