LeetCode-----4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays.The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3] nums2 = [2] The median is 2.0

Example 2:

nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5

Subscribe to see which companies asked this question

快速排序实现思路。

①以第一个关键字 K 1 为控制字，将 [K 1 ,K 2 ,…,K n ] 分成两个子区，使左区所有关键字小于等于 K 1 ，右区所有关键字大于等于 K 1 ，最后控制字居两个子区中间的适当位置。在子区内数据尚处于无序状态。  ②把左区作为一个整体，用①的步骤进行处理，右区进行相同的处理。（即递归） ③重复第①、②步，直到左区处理完毕。

编写：

把整个序列看做一个数组，把第零个位置看做中轴，和最后一个比，如果比它小交换，比它大不做任何处理；交换了以后再和小的那端比，比它小不交换，比他大交换。这样循环往复，一趟排序完成，左边就是比中轴小的，右边就是比中轴大的，然后再用分治法，分别对这两个独立的数组进行排序。

static void quicksort(int n[], int left, int right) { int dp; if (left < right) { dp = partition(n, left, right); quicksort(n, left, dp - 1); quicksort(n, dp + 1, right); } } static int partition(int n[], int left, int right) { int pivot = n[left]; while (left < right) { while (left < right && n[right] >= pivot) right--; if (left < right) n[left++] = n[right]; while (left < right && n[left] <= pivot) left++; if (left < right) n[right--] = n[left]; } n[left] = pivot; return left; }

//找到已排序数组的中位数；快排递归深度 public class Solution { public static int[] C; public static void quickSort(int a[],int low, int high){ if(low < high){ int i = low; int tmp; for(int j = low; j< high; j++){ if(a[j]<=a[high]){ tmp = a[i]; a[i] = a[j]; a[j] = tmp; ++ i; } } tmp = a[i]; a[i] = a[high]; a[high] = tmp; quickSort(a,low,i-1); quickSort(a,i+1,high); } } public static double findMedianSortedArrays(int A[], int B[]) { double i ; //combine these two arrays into a new array C int l = A.length+B.length; C = new int[l]; System.arraycopy(A, 0, C, 0, A.length); System.arraycopy(B, 0, C, A.length, B.length); quickSort(C,0,l-1); //for(int ii = 0; ii < l; ii ++) //System.out.println(C[ii]); if(l%2 == 0) i = (double) ((C[l/2]+C[l/2-1])/2.0); else i = (double) C[(l-1)/2]; return i; } public static void main(String args[]){ int[] A = {1}; int[] B = {}; double median = findMedianSortedArrays(A,B); System.out.println(median); } }