중앙값은 중간 숫자입니다. 즉, 중앙값은 정렬된 목록의 중간 관측값입니다. 50%의 누적 백분율에 해당합니다.
두 배열의 크기는 같아야 합니다. 처음에는 두 개의 개별 배열의 중앙값을 찾은 다음 개별 중앙값을 비교하여 두 목록의 실제 중앙값을 구합니다.
입력 및 출력
Input: Two sorted array are given. Array 1: {1, 2, 3, 6, 7} Array 2: {4, 6, 8, 10, 11} Output: The median from two array. Here the median value is 6. Merge the given lists into one. {1, 2, 3, 4, 6, 6, 7, 8, 10, 11} From the merged list find the average of two middle elements. here (6+6)/2 = 6.
알고리즘
중앙값(목록, n)
입력: 데이터 목록 및 데이터 수입니다.
출력: 주어진 목록의 중앙값입니다.
Begin if the list has even number of data, then return (list[n/2] + list[n/2-1])/2 else return list[n/2] End
findMedian(list1, list2, n)
입력 - 두 개의 정렬된 목록과 목록의 수입니다.
출력 - 정렬된 두 목록의 중앙값입니다.
Begin if n <= 0, then it is invalid, and return invalid number if n = 1, then return (list1[0] + list2[0])/2 if n = 2, then return ((max of list1[0], list2[0]) + (min of list1[1], list2[1]))/2 med1 := median(list1, n) med2 := median(list2, n) if med1 = med2, then return med1 if med1 < med2, then if item has even number of data, then subList := data from list2, from 0 to n/2 – 1 data return findMedian(subList, list1, n – (n/2) + 1) subList := data from list2, from 0 to n/2 data return findMedian(subList, list2, n – (n/2)) End
예시
#include<iostream> using namespace std; int median(int list[], int n) { if (n%2 == 0) //when array containts even number of data return (list[n/2] + list[n/2-1])/2; else //for odd number of data return list[n/2]; } intfindMedian(int list1[], int list2[], int n) { if (n <= 0) return -1; //invalid length of lists if (n == 1) return (list1[0] + list2[0])/2; //for single element simply get average from two array if (n == 2) return (max(list1[0], list2[0]) + min(list1[1], list2[1])) / 2; int med1 = median(list1, n); //Find median from first array int med2 = median(list2, n); //Find median from second array if (med1 == med2) //when both medians are same, they are the final median return med1; if (med1 < med2) { if (n % 2 == 0) return findMedian(list1 + n/2 - 1, list2, n - n/2 +1); return findMedian(list1 + n/2, list2, n - n/2); } if (n % 2 == 0) //when med1 > med2 return findMedian(list2 + n/2 - 1, list1, n - n/2 + 1); return findMedian(list2 + n/2, list1, n - n/2); } int main() { int list1[] = {1, 2, 3, 6, 7}; int list2[] = {4, 6, 8, 10, 11}; int n1 = 5; int n2 = 5; if (n1 == n2) cout<< "Median is "<<findMedian(list1, list2, n1); else cout<< "Doesn't work for lists of unequal size"; }
출력
Median is 6