Tìm trung vị của hai mảng đã sắp xếp

Trung vị là số nằm giữa trong một danh sách đã được sắp xếp theo thứ tự. Nói cách khác, giá trị trung vị là quan sát chính giữa trong danh sách có thứ tự, tương ứng với tỷ lệ tích lũy 50%.

Đầu vào và Đầu ra

Đầu vào: Hai mảng đã sắp xếp. Mảng 1: {1, 2, 3, 6, 7} Mảng 2: {4, 6, 8, 10, 11}
Đầu ra: Trung vị của hai mảng. Ở đây giá trị trung vị là 6.
Gộp hai danh sách thành một: {1, 2, 3, 4, 6, 6, 7, 8, 10, 11}
Từ danh sách đã gộp, tìm trung bình cộng của hai phần tử ở giữa: (6+6)/2 = 6.

Thuật toán

median(list, n)

Đầu vào: Danh sách dữ liệu và số lượng phần tử.

Đầu ra: Trung vị của danh sách cho trước.

Bắt đầu
  nếu danh sách có số lượng phần tử chẵn thì
    trả về (list[n/2] + list[n/2-1])/2
  ngược lại
    trả về list[n/2]
Kết thúc

findMedian(list1, list2, n)

Đầu vào: Hai danh sách đã sắp xếp và số lượng phần tử của mỗi danh sách.

Đầu ra: Trung vị từ hai danh sách đã sắp xếp.

Bắt đầu
  nếu n <= 0 thì
    không hợp lệ, trả về số không hợp lệ
  nếu n = 1 thì
    trả về (list1[0] + list2[0])/2
  nếu n = 2 thì
    trả về ((max của list1[0], list2[0]) + (min của list1[1], list2[1]))/2
  med1 := median(list1, n)
  med2 := median(list2, n)
  nếu med1 = med2 thì
    trả về med1
  nếu med1 < med2 thì
    nếu số phần tử chẵn thì
      subList := dữ liệu từ list2, từ 0 đến n/2 - 1
      trả về findMedian(subList, list1, n - (n/2) + 1)
    ngược lại
      subList := dữ liệu từ list2, từ 0 đến n/2
      trả về findMedian(subList, list2, n - (n/2))
  ngược lại (med1 > med2)
    nếu số phần tử chẵn thì
      trả về findMedian(list2 + n/2 - 1, list1, n - n/2 + 1)
    ngược lại
      trả về findMedian(list2 + n/2, list1, n - n/2)
Kết thúc

Ví dụ (C++)

#include <iostream>
using namespace std;

int median(int list[], int n) {
  if (n % 2 == 0) // khi mảng chứa số lượng dữ liệu chẵn
    return (list[n/2] + list[n/2-1])/2;
  else // cho số lượng dữ liệu lẻ
    return list[n/2];
}

int findMedian(int list1[], int list2[], int n) {
  if (n <= 0)
    return -1; // độ dài danh sách không hợp lệ
  if (n == 1)
    return (list1[0] + list2[0])/2; // với một phần tử, lấy trung bình từ hai mảng
  if (n == 2)
    return (max(list1[0], list2[0]) + min(list1[1], list2[1])) / 2;
  
  int med1 = median(list1, n); // Tìm trung vị từ mảng đầu tiên
  int med2 = median(list2, n); // Tìm trung vị từ mảng thứ hai
  
  if (med1 == med2) // khi cả hai trung vị giống nhau, đó là trung vị cuối cùng
    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);
  }
  
  // khi med1 > med2
  if (n % 2 == 0)
    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";
}

Đầu ra

Median is 6