使用快速选择算法的未排序数组的中位数

2021年4月26日16:19:43 发表评论 929 次浏览

本文概述

给定一个长度为N的未排序数组arr[]，任务是找到这个数组的中位数。

一个大小为N的有序数组的中位数定义为N为奇数时的中间元素，N为偶数时的中间两个元素的平均值。

例子：

输入：arr [] = {12, 3, 5, 7, 4, 19, 26}
输出：7
给定数组arr [] = {3, 4, 5, 7, 12, 19, 26}的排序序列
元素数量为奇数, 中位数为给定数组arr []的排序序列中的第4个元素, 即7
输入：arr [] = {12, 3, 5, 7, 4, 26}
输出：6
元素是偶数, 中位数是给定数组arr []的排序序列中第3个元素和第4个元素的平均值, 这意味着(5 + 7)/ 2 = 6

简单的方法：

  • 对数组排序arr []按升序排列。
  • 如果元素数量arr []是奇数, 则中位数是arr [n / 2].
  • 如果元素数arr []是偶数, 中位数是arr [n / 2]和arr [n / 2 + 1]的平均值.

以上方法的实现请参阅本文。

有效方法:使用随机快速选择

  • 从中随机选择枢轴元素arr []和使用分割步骤来自快速排序算法将所有小于枢轴的元素排列在其左侧, 并将所有元素大于其枢轴排列在其右侧。
  • 如果在上一步之后, 所选枢轴的位置在数组的中间, 则它是给定数组的所需中间值。
  • 如果位置在中间元素之前, 则对子数组重复该步骤, 从先前的起始索引开始, 然后将所选的枢轴作为结束索引。
  • 如果位置在中间元素之后, 则对子数组重复该步骤, 从选定的枢轴开始, 到上一个结束索引结束。
  • 请注意, 在偶数个元素的情况下, 必须找到中间两个元素, 它们的平均值将是数组的中位数。

下面是上述方法的实现：

C ++

//CPP program to find median of
//an array
 
#include "bits/stdc++.h"
using namespace std;
 
//Utility function to swapping of element
void swap( int * a, int * b)
{
     int temp = *a;
     *a = *b;
     *b = temp;
}
 
//Returns the correct position of
//pivot element
int Partition( int arr[], int l, int r)
{
     int lst = arr[r], i = l, j = l;
     while (j <r) {
         if (arr[j] <lst) {
             swap(&arr[i], &arr[j]);
             i++;
         }
         j++;
     }
     swap(&arr[i], &arr[r]);
     return i;
}
 
//Picks a random pivot element between
//l and r and partitions arr[l..r]
//around the randomly picked element
//using partition()
int randomPartition( int arr[], int l, int r)
{
     int n = r - l + 1;
     int pivot = rand () % n;
     swap(&arr[l + pivot], &arr[r]);
     return Partition(arr, l, r);
}
 
//Utility function to find median
void MedianUtil( int arr[], int l, int r, int k, int & a, int & b)
{
 
     //if l <r
     if (l <= r) {
 
         //Find the partition index
         int partitionIndex
             = randomPartition(arr, l, r);
 
         //If partion index = k, then
         //we found the median of odd
         //number element in arr[]
         if (partitionIndex == k) {
             b = arr[partitionIndex];
             if (a != -1)
                 return ;
         }
 
         //If index = k - 1, then we get
         //a & b as middle element of
         //arr[]
         else if (partitionIndex == k - 1) {
             a = arr[partitionIndex];
             if (b != -1)
                 return ;
         }
 
         //If partitionIndex>= k then
         //find the index in first half
         //of the arr[]
         if (partitionIndex>= k)
             return MedianUtil(arr, l, partitionIndex - 1, k, a, b);
 
         //If partitionIndex <= k then
         //find the index in second half
         //of the arr[]
         else
             return MedianUtil(arr, partitionIndex + 1, r, k, a, b);
     }
 
     return ;
}
 
//Function to find Median
void findMedian( int arr[], int n)
{
     int ans, a = -1, b = -1;
 
     //If n is odd
     if (n % 2 == 1) {
         MedianUtil(arr, 0, n - 1, n /2, a, b);
         ans = b;
     }
 
     //If n is even
     else {
         MedianUtil(arr, 0, n - 1, n /2, a, b);
         ans = (a + b) /2;
     }
 
     //Print the Median of arr[]
     cout <<"Median = " <<ans;
}
 
//Driver program to test above methods
int main()
{
     int arr[] = { 12, 3, 5, 7, 4, 19, 26 };
     int n = sizeof (arr) /sizeof (arr[0]);
     findMedian(arr, n);
     return 0;
}

Java

//JAVA program to find median of
//an array
class GFG
{
     static int a, b;
 
     //Utility function to swapping of element
     static int [] swap( int [] arr, int i, int j)
     {
         int temp = arr[i];
         arr[i] = arr[j];
         arr[j] = temp;
         return arr;
     }
 
     //Returns the correct position of
     //pivot element
     static int Partition( int arr[], int l, int r)
     {
         int lst = arr[r], i = l, j = l;
         while (j <r)
         {
             if (arr[j] <lst)
             {
                 arr = swap(arr, i, j);
                 i++;
             }
             j++;
         }
         arr = swap(arr, i, r);
         return i;
     }
 
     //Picks a random pivot element between
     //l and r and partitions arr[l..r]
     //around the randomly picked element
     //using partition()
     static int randomPartition( int arr[], int l, int r)
     {
         int n = r - l + 1 ;
         int pivot = ( int ) (Math.random() % n);
         arr = swap(arr, l + pivot, r);
         return Partition(arr, l, r);
     }
 
     //Utility function to find median
     static int MedianUtil( int arr[], int l, int r, int k)
     {
 
         //if l <r
         if (l <= r)
         {
 
             //Find the partition index
             int partitionIndex = randomPartition(arr, l, r);
 
             //If partion index = k, then
             //we found the median of odd
             //number element in arr[]
             if (partitionIndex == k)
             {
                 b = arr[partitionIndex];
                 if (a != - 1 )
                     return Integer.MIN_VALUE;
             }
 
             //If index = k - 1, then we get
             //a & b as middle element of
             //arr[]
             else if (partitionIndex == k - 1 )
             {
                 a = arr[partitionIndex];
                 if (b != - 1 )
                     return Integer.MIN_VALUE;
             }
 
             //If partitionIndex>= k then
             //find the index in first half
             //of the arr[]
             if (partitionIndex>= k)
                 return MedianUtil(arr, l, partitionIndex - 1 , k);
 
             //If partitionIndex <= k then
             //find the index in second half
             //of the arr[]
             else
                 return MedianUtil(arr, partitionIndex + 1 , r, k);
         }
 
         return Integer.MIN_VALUE;
     }
 
     //Function to find Median
     static void findMedian( int arr[], int n)
     {
         int ans;
         a = - 1 ;
         b = - 1 ;
 
         //If n is odd
         if (n % 2 == 1 )
         {
             MedianUtil(arr, 0 , n - 1 , n /2 );
             ans = b;
         }
 
         //If n is even
         else
         {
             MedianUtil(arr, 0 , n - 1 , n /2 );
             ans = (a + b) /2 ;
         }
 
         //Print the Median of arr[]
         System.out.print( "Median = " + ans);
     }
 
     //Driver code
     public static void main(String[] args)
     {
         int arr[] = { 12 , 3 , 5 , 7 , 4 , 19 , 26 };
         int n = arr.length;
         findMedian(arr, n);
     }
}
 
//This code is contributed by 29AjayKumar

Python3

# Python3 program to find median of
# an array
import random
 
a, b = None , None ;
 
# Returns the correct position of
# pivot element
def Partition(arr, l, r) :
 
     lst = arr[r]; i = l; j = l;
     while (j <r) :
         if (arr[j] <lst) :
             arr[i], arr[j] = arr[j], arr[i];
             i + = 1 ;
         
         j + = 1 ;
 
     arr[i], arr[r] = arr[r], arr[i];
     return i;
 
# Picks a random pivot element between
# l and r and partitions arr[l..r]
# around the randomly picked element
# using partition()
def randomPartition(arr, l, r) :
     n = r - l + 1 ;
     pivot = random.randrange( 1 , 100 ) % n;
     arr[l + pivot], arr[r] = arr[r], arr[l + pivot];
     return Partition(arr, l, r);
 
# Utility function to find median
def MedianUtil(arr, l, r, k, a1, b1) :
 
     global a, b;
     
     # if l <r
     if (l <= r) :
         
         # Find the partition index
         partitionIndex = randomPartition(arr, l, r);
         
         # If partion index = k, then
         # we found the median of odd
         # number element in arr[]
         if (partitionIndex = = k) :
             b = arr[partitionIndex];
             if (a1 ! = - 1 ) :
                 return ;
                 
         # If index = k - 1, then we get
         # a & b as middle element of
         # arr[]
         elif (partitionIndex = = k - 1 ) :
             a = arr[partitionIndex];
             if (b1 ! = - 1 ) :
                 return ;
                 
         # If partitionIndex>= k then
         # find the index in first half
         # of the arr[]
         if (partitionIndex> = k) :
             return MedianUtil(arr, l, partitionIndex - 1 , k, a, b);
             
         # If partitionIndex <= k then
         # find the index in second half
         # of the arr[]
         else :
             return MedianUtil(arr, partitionIndex + 1 , r, k, a, b);
             
     return ;
 
# Function to find Median
def findMedian(arr, n) :
     global a;
     global b;
     a = - 1 ;
     b = - 1 ;
     
     # If n is odd
     if (n % 2 = = 1 ) :
         MedianUtil(arr, 0 , n - 1 , n //2 , a, b);
         ans = b;
         
     # If n is even
     else :
         MedianUtil(arr, 0 , n - 1 , n //2 , a, b);
         ans = (a + b) //2 ;
         
     # Print the Median of arr[]
     print ( "Median = " , ans);
 
 
# Driver code
arr = [ 12 , 3 , 5 , 7 , 4 , 19 , 26 ];
n = len (arr);
findMedian(arr, n);
 
# This code is contributed by AnkitRai01

C#

//C# program to find median of
//an array
using System;
 
class GFG
{
     static int a, b;
 
     //Utility function to swapping of element
     static int [] swap( int [] arr, int i, int j)
     {
         int temp = arr[i];
         arr[i] = arr[j];
         arr[j] = temp;
         return arr;
     }
 
     //Returns the correct position of
     //pivot element
     static int Partition( int []arr, int l, int r)
     {
         int lst = arr[r], i = l, j = l;
         while (j <r)
         {
             if (arr[j] <lst)
             {
                 arr = swap(arr, i, j);
                 i++;
             }
             j++;
         }
         arr = swap(arr, i, r);
         return i;
     }
 
     //Picks a random pivot element between
     //l and r and partitions arr[l..r]
     //around the randomly picked element
     //using partition()
     static int randomPartition( int []arr, int l, int r)
     {
         int n = r - l + 1;
         int pivot = ( int ) ( new Random().Next() % n);
         arr = swap(arr, l + pivot, r);
         return Partition(arr, l, r);
     }
 
     //Utility function to find median
     static int MedianUtil( int []arr, int l, int r, int k)
     {
 
         //if l <r
         if (l <= r)
         {
 
             //Find the partition index
             int partitionIndex = randomPartition(arr, l, r);
 
             //If partion index = k, then
             //we found the median of odd
             //number element in []arr
             if (partitionIndex == k)
             {
                 b = arr[partitionIndex];
                 if (a != -1)
                     return int .MinValue;
             }
 
             //If index = k - 1, then we get
             //a & b as middle element of
             //[]arr
             else if (partitionIndex == k - 1)
             {
                 a = arr[partitionIndex];
                 if (b != -1)
                     return int .MinValue;
             }
 
             //If partitionIndex>= k then
             //find the index in first half
             //of the []arr
             if (partitionIndex>= k)
                 return MedianUtil(arr, l, partitionIndex - 1, k);
 
             //If partitionIndex <= k then
             //find the index in second half
             //of the []arr
             else
                 return MedianUtil(arr, partitionIndex + 1, r, k);
         }
 
         return int .MinValue;
     }
 
     //Function to find Median
     static void findMedian( int []arr, int n)
     {
         int ans;
         a = -1;
         b = -1;
 
         //If n is odd
         if (n % 2 == 1)
         {
             MedianUtil(arr, 0, n - 1, n /2);
             ans = b;
         }
 
         //If n is even
         else
         {
             MedianUtil(arr, 0, n - 1, n /2);
             ans = (a + b) /2;
         }
 
         //Print the Median of []arr
         Console.Write( "Median = " + ans);
     }
 
     //Driver code
     public static void Main(String[] args)
     {
         int []arr = { 12, 3, 5, 7, 4, 19, 26 };
         int n = arr.Length;
         findMedian(arr, n);
     }
}
 
//This code is contributed by PrinciRaj1992

输出如下：

Median = 7

时间复杂度：

  1. 最佳案例分析：O(1)
  2. 平均案例分析：O(N)
  3. 最坏情况分析：O(N2)

想知道如何？

参考：斯坦福大学

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: