1
pwrliang 2018-03-24 08:54:50 +08:00 via Android
把两个有序数组接起来,然后用快排的分区函数的找中位数?楼下继续…
|
2
pkookp8 2018-03-24 08:57:51 +08:00 via Android
这是 leetcode 的题目吗,好像见过。有序数组归并排序。总数除以二得到中位数。区分总数奇偶
|
5
wingkou 2018-03-24 09:00:43 +08:00 via Android
考研 408 真题哈哈哈
|
6
lhx2008 2018-03-24 09:02:03 +08:00
应该考的是归并排序了,但是好像直接连接排序也没多慢
|
7
lhx2008 2018-03-24 09:05:16 +08:00
有序的话,也可以分类讨论下 nums2 是在 num1 的左边、中间还是右边,然后一次拼接上去
|
9
Andiry 2018-03-24 09:12:49 +08:00
显然这题考的不是排序
|
10
lhx2008 2018-03-24 09:18:15 +08:00
'''java
class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int length = nums1.length + nums2.length; int[] nums = new int[length]; System.arraycopy(nums1,0,nums,0,nums1.length); System.arraycopy(nums2,0,nums,nums1.length,nums2.length); Arrays.sort(nums); if (length % 2 == 0) { return ((double)(nums[length/2] + nums[length/2 - 1]))/2; } else { return nums[length/2]; } } } ''' emmm...输入复杂度最优, 提交了三次,最多可以 beats 85.52% (67 ms) |
11
lhx2008 2018-03-24 09:43:56 +08:00
"""java
class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int length = nums1.length + nums2.length; int[] arr = new int[length]; int i = 0,j = 0; //nums1,nums2 for( int k = 0 ; k < length; k ++ ){ if( i >= nums1.length ){ arr[k] = nums2[j]; j ++; } else if( j >= nums2.length ){ arr[k] = nums1[i]; i ++; } else if(nums1[i] < nums2[j]){ arr[k] = nums1[i]; i ++; } else{ arr[k] = nums2[j]; j ++; } } if (length % 2 == 0) { return ((double)(arr[length/2] + arr[length/2 - 1]))/2; } else { return arr[length/2]; } } } """ 不调系统函数耍流氓的方法,但是其实没有上面那个那么快,提交三次最快也就 68ms, beats 84% 一个原因是 System.arraycopy 是 jvm 实现的,比赋值快得多,Arrays.sort 也不慢 在 leetcode 上面也看了很多复杂的答案,但是至少在 leetcode 的测试用例来说,那一点时间复杂度优势相当于没有。当然其他情况不好说,要看什么地方用 |
12
victor97 2018-03-24 10:27:04 +08:00
题目都说了要 O(log(m+n))的做法了。排序应该是不行的。
有个 O(log(n+m))的做法是,在 nums1 二分查找一个数,二分判断其在 nums2 的位置,从而得知合并后它的位置,判断是否是中位数。 |
13
zqqian 2018-03-24 10:28:09 +08:00
如果总长度是奇数
分别二分 num1 和 num2 对每个二分数 x 检查 num1 中小于 x 的数目+num2 中小于 x 的数目 是不是等于总长度的一半 如果总长度是偶数 二分 num1 然后取 num2 中与 num1 中的二分值相邻的两个数。 分别检查 |
14
pwrliang 2018-03-25 05:56:32 +08:00
我来实现一下一楼我说的方法吧,首先解决一个数组找中位数的问题
对于 len % 2 == 0,我们求出数组第 len / 2 大的数和 len / 2 + 1 大的数,再求和除以 2 就是中位数,对于 len % 2 == 1 的情况,直接找 len / 2 + 1 大的数就是中位数。 至于怎么求第 k 大的数( top 问题),可以用快排的分区函数来实现。https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/ 以下代码通过了 leetcode judege: class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int[] cpy = new int[nums1.length + nums2.length]; System.arraycopy(nums1, 0, cpy, 0, nums1.length); System.arraycopy(nums2, 0, cpy, nums1.length, nums2.length); return findForOne(cpy); } double findForOne(int[] nums) { if (nums.length % 2 == 0) { int k1 = getKth(nums, 0, nums.length - 1, nums.length / 2); int k2 = getKth(nums, 0, nums.length - 1, nums.length / 2 + 1); return (k1 + k2) / 2.0; } return getKth(nums, 0, nums.length - 1, nums.length / 2 + 1); } int getKth(int[] nums, int lo, int hi, int k) { int ans = Integer.MAX_VALUE; if (k > 0 && k <= hi - lo + 1) { int pos = partition(nums, lo, hi); int len = pos - lo; if (len == k - 1) ans = nums[pos]; else if (k - 1 < len) ans = getKth(nums, lo, pos - 1, k); else ans = getKth(nums, pos + 1, hi, k - len - 1); } return ans; } int partition(int arr[], int l, int r) { int x = arr[r], i = l; for (int j = l; j <= r - 1; j++) { if (arr[j] <= x) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; i++; } } int tmp = arr[i]; arr[i] = arr[r]; arr[r] = tmp; return i; } } |
15
pwrliang 2018-03-25 09:41:55 +08:00 1
更新一下,上面的 top k 算法我摘自 geekforgeek 的,其实我并没有看懂。下面的找 top k 算法来自《算法 第四版》,这个代码更易读懂,运行时间也比上面的代码更短。
两个数组拼凑需要 O(m+n),如果是偶数长度,查找两次 top k 需要 O(2*(m+n)),奇数长度 O(m+n),因此时间复杂度在 O(2*(m+n))~O(3*(m+n))之间。 当然另一种方法是用两个指针指向两个数组当前元素,依次将当前最小的元素写入第三个数组,即合并两个有序数组生成的数组也是有序的。然后再找中位数。 public double findMedianSortedArrays(int[] nums1, int[] nums2) { int[] cpy = new int[nums1.length + nums2.length]; System.arraycopy(nums1, 0, cpy, 0, nums1.length); System.arraycopy(nums2, 0, cpy, nums1.length, nums2.length); return findForOne(cpy); } double findForOne(int[] nums) { if (nums.length % 2 == 0) { int k1 = getKth(nums, nums.length / 2 - 1); int k2 = getKth(nums, nums.length / 2); return (k1 + k2) / 2.0; } return getKth(nums, nums.length / 2); } //2 1 3 4 5 int getKth(int[] nums, int k) { int lo = 0, hi = nums.length - 1; while (lo < hi) { int j = partition(nums, lo, hi); if (j < k) lo = j + 1; else if (j > k) hi = j - 1; else { return nums[k]; } } return nums[k]; } int partition(int[] nums, int lo, int hi) { int pivot = nums[lo]; int i = lo, j = hi + 1; while (true) { while (nums[++i] < pivot) if (i == hi) break; while (nums[--j] > pivot) if (j == lo) break; if (i >= j) break; int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } int tmp = nums[lo]; nums[lo] = nums[j]; nums[j] = tmp; return j; } |