-
2019-02-24 20:48:41
类似于快速排序那种,只不过另加处理一番。
附上代码:
#include<bits/stdc++.h> using namespace std; const int maxn=1e2+5; int n,a[maxn]; double select_middle(int beg,int end) { if(n==1)return a[0]; int i=beg; for(int j=i+1;j<=end;j++){ if(a[j]<a[beg]){ ++i; swap(a[i],a[j]); } } swap(a[beg],a[i]); if(i<n/2)return select_middle(i+1,end); else if(i>n/2)return select_middle(beg,i-1); else{ if(n%2)return a[i]; else{ int m=a[0]; for(int j=1;j<i;j++){ if(a[j]>m){ m=a[j]; } } return (double)(a[i]+m)/2; } } } int main() { scanf("%d",&n); for(int i=0;i<n;i++)scanf("%d",&a[i]); printf("%f\n",select_middle(0,n-1)); return 0; } /* 5 3 2 1 4 5 4 2 1 3 4 */
更多相关内容 -
O(n)的时间复杂度求中位数
2020-09-26 14:45:14O(n)中位数问题是指:在O(n)的时间复杂度内找到一个无序序列的中位数。 在开始O(n)时间复杂度求中位数之前,先手写一下快速排序。 快速排序的实现 Reference: 快速排序|菜鸟教程 白话经典算法系列之六 快速排序 ...O(n)的时间复杂度求中位数
O(n)
中位数问题是指:在O(n)
的时间复杂度内找到一个无序序列的中位数。在开始
O(n)
时间复杂度求中位数之前,先手写一下快速排序。快速排序的实现
Reference:
快速排序|菜鸟教程
白话经典算法系列之六 快速排序 快速搞定快速排序的原理
如果想正序排序一个序列:
- 从序列中找到一个 基准数 。
- 分区:将序列中比基准数大的数字都放到基准数的右边,将序列中比基准数小的数字都放在基准数的左边。
- 此时,序列被分成了三部分:
左序列
+基准数
+右序列
。 - 实现
2
的方法可以是 挖坑法 。
- 此时,序列被分成了三部分:
- 对左序列和有序列进行排序即可(递归),直到左/右序列长度为
1
。
快速排序的复杂度
- 时间复杂度:
- 最好:
O(nlogn)
- 最坏:
O(n^2)
- 平均:
O(nlogn)
- 最好:
- 空间复杂度:
O(nlogn)
- 稳定性:不稳定
快速排序的实现1
void quick_sort(int a[], int left, int right){ if (left >= right){ return; } int l = left, r = right; int x = a[left]; // 选取当前序列最左边的数字为基准数 while (l < r){ while (l < r && a[r] >= x){ r --; } if (l < r){ a[l] = a[r]; l ++; } while (l < r && a[l] < x){ l ++; } if (l < r){ a[r] = a[l]; r ++; } } a[l] = x; quick_sort(a, left, l - 1); quick_sort(a, l + 1, right); }
- 每一次快排都会确定一个位置,这个位置是
l
,大小是基准数
。 - 如果我们想每一次都知道 快速排序确定的位置 ,那么可以写一个
partition函数
。(事实上,这是在为O(n)解决中位数问题做铺垫。)
快速排序的实现2——partition函数
int partition(int a[], int l, int r){ int x = a[l]; while (l < r){ while (l < r && a[r] >= x){ r --; } if (l < r){ a[l] = a[r]; l ++; } while (l < r && a[l] < x){ l ++; } if (l < r){ a[r] = a[l]; r --; } } a[l] = x; return l; } void Q_sort(int a[], int l, int r){ if (l < r){ int index = partition(a, l, r); Q_sort(a, l, index-1); Q_sort(a, index+1, r); } }
-
partiton()
负责将获得每一次进行步骤2:分区
得到的基准数
在最终递增序列中的 位置 。 -
Q_sort()
中的index
就是该位置。根据该位置将序列分为左右序列。
有了
partition
函数,就可以实现O(n)
时间复杂度找中位数的工作了。基于partition函数的O(n)中位数
显然,如果没有
O(n)
的限制,那么一个直白的想法是:将无序序列排序,然后输出序列的 第n/2
个位置 的元素。n
是序列的长度。- 其实,对于中位数应该分情况讨论:
- 当
n
是奇数时,中位数是a[n/2]
; - 当
n
是偶数时,中位数是(a[n/2] + a[n/2 - 1]) / 2.0
。
- 当
上述算法的时间复杂度是
O(nlogn)
。考虑到,对于partition函数,每一个可以确定一个位置! 那么,假设这个位置是
index
,那么对于中位数的位置pos
:- 如果
index = pos
,显然,找到了中位数a[index]
。 - 如果
index > pos
,显然,中位数位于区间[l, index-1]
。- 此时,只需对区间
[l, index-1]
再次进行partition
操作即可。
- 此时,只需对区间
- 如果
index < pos
,显然,中位数位于区间[index+1, r]
。- 同上。
根据上述思想,编写函数
getMidNumber()
:int getMidNumber(int a[], int l, int r, int pos){ while (true){ int index = partition(a, l, r); // 获得基准数的位置 if (index == pos){ return a[index]; }else if (index > pos){ // 只需要在[l, index-1]区间内找pos位置即可 r = index - 1; }else { // 只需要在[index, r]区间内找pos位置即可 l = index + 1; } } return -1; // 一般程序不会到这里 }
- 其中,
pos
的含义是中位数的位置:- 当序列长度为奇数时,pos = n/2
- 当序列长度为偶数时,pos = n/2 或 n/2 - 1
比如,可以编写如下代码测试:
int main(){ int a[] = {10, 8, 3, 5, 6, 2, 1, 7, 9, 4}; int aLen = sizeof(a) / sizeof(int); if (aLen&1){ cout << "Mid= " << getMidNumber(a, 0, aLen-1, aLen/2) << endl; }else{ cout << "Mid= " << (getMidNumber(a, 0, aLen-1, aLen/2) + getMidNumber(a, 0, aLen-1, aLen/2-1)) / 2.0 << endl; } return 0; }
aLen
是序列a
的长度。
时间复杂度分析
最坏:
O(n^2)
- 假设一种极端情况,每一次选取的基准数都是序列中最小的那个数字,因此partition函数会依次返回
0,1,2...n/2
,每一次partition函数都需要O(n)
的时间复杂度。因此,最坏的时间复杂度为O(n^2)
。
最好:
O(n)
- 假设一种完美情况,第一次得到的基准数就是中位数,那么只需要执行一次partition函数,因此时间复杂度是
O(n)
。
平均:
O(n)
数学不好,证明不会。据 他们 说该算法的 期望 时间复杂度是O(n)
。
这好像是涉及 主定理MasterTheorem。搜了好多网页博客也没看懂。Reference:
主定理 Master Theorem拓展:找序列中第
K
大的数字其实找中位数就是找序列中第
n/2
大的数字。因此找需要调用
getMidNumber(a, 0, aLen-1, k)
即可找到序列中第k
大的数字了。大佬的一种更简洁的写法
2020.9.26 14:41 周六
-
寻找两个有序数组的中位数(附上三种解法)
2019-12-06 18:23:32测试结果:则中位数是 2.0 •解法一 怎么说解法一呢,其实可以把解法一当成暴力解法,对这道题进行硬解。但是如果仔细看要求的话就会发现,题目里要求了时间复杂度是O(log(m + n)),所以这种解法不能满足要求...目录
•写在前面
这道题比较经典,我当时在做的时候,想出了两种解决方案,不过总感觉算法不够优美,所以找到了另一种我觉得非常精妙的解法,利用了K最小数的思想去解决这道题,很值得讲一下,不知道K最小数的,可以参考我另一篇文章,点击这里跳转就可以了。下面我废话不多说,直接开始讲解。
•题目
首先先把题目呈上来,具体题目如下:
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请你找出这两个有序 数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。你可以假 设 nums1 和 nums2 不会同时为空。 测试用例: nums1 = [1, 3] nums2 = [2] 测试结果:则中位数是 2.0
•解法一
怎么说解法一呢,其实可以把解法一当成暴力解法,对这道题进行硬解。但是如果仔细看要求的话就会发现,题目里要求了时间复杂度是O(log(m + n)),所以这种解法不能满足要求,不过因为我当时先看到的是没有O(log(m + n))要求的题目,所以就直接暴力解决了(对于有些题目,暴力不失为一种省力的好办法,小声bb)。这个解法没什么好讲的,我就大概说一下思路。
具体思路就是,将两个数组使用归并的思想,进行整合,然后求解。(ps:别说直接合起来,然后排序,你要是这样做的话,算法老师的棺材板都压不住),直接上代码。当然啦,下面代码直接整合成了一个数组,其实我们也可以不用真的整合数组,只要通过不断比对,然后记录值就可以了(注意边界问题)。这种解法的时间复杂度是O(m + n)哦。
public static double Test4S2(int[] nums1, int[] nums2) { List<Integer> array = new ArrayList<>(10); int size1 = nums1.length; int size2 = nums2.length; int index1 = 0; int index2 = 0; while(index1 != size1 || index2 != size2){ if(index1 == size1){ for (int i = index2; i < size2; i++){ array.add(nums2[i]); } break; }else if (index2 == size2){ for (int i = index1; i < size1; i++){ array.add(nums1[i]); } break; } array.add(nums1[index1] < nums2[index2] ? nums1[index1] : nums2[index2]); if(nums1[index1] < nums2[index2]){ if(index1 < size1) index1++; } else{ if(index2 < size2) index2++; } } int sizeArray = array.size() / 2; if(array.size() % 2 == 0) return (array.get(sizeArray - 1) + array.get(sizeArray)) / 2.00; else return array.get(sizeArray); }
•解法二
在考虑题目时间复杂度O(log(m + n))的情况下,我换了一种解法,这种解法也没啥精妙的地方,主要是对中位数的概念理解好了,就容易想到。首先很多时候,我们看到了log一般就要想到二分法。
具体思路,中位数的概念其实可以理解为,将数组整体分为两个部分,一边大于等于中位数,一边小于等于中位数。那么在这道题目中两个有序数组,我们可以将两个数组并排画一条线,这条线能正好划分左右两个部分,而我们的任务就是要找到这条线。可能形容起来比较吃力,话不多说,上图看。
就是为了找到i,j连起来的线,能够正好将两个数组划分成左右两个部分,划分好了之后,只需要记录左边最大的值和右边最小的值,通过这两个值求解中位数就可以了,研究之后你就会发现i和j的关系是
i + j = m - i + n - j
因为左边部分和右边部分的数量要相等,有了这个之后,我们只要最开始随机确定i(直接在小数组中间取i),然后通过左右移动i(j移动的方向和i相反)找到我们要的那条线。不过一定要小心边界问题,对于边界要进行处理好哦。代码如下
public static double Test4S3(int[] nums1, int[] nums2) { int m = nums1.length; int n = nums2.length; if (m > n) { return Test4S3(nums2,nums1); // 保证 m <= n } int iMin = 0, iMax = m; while (iMin <= iMax) { int i = (iMin + iMax) / 2; int j = (m + n + 1) / 2 - i; if (j != 0 && i != m && nums2[j-1] > nums1[i]){ // i 需要增大 iMin = i + 1; } else if (i != 0 && j != n && nums1[i-1] > nums2[j]) { // i 需要减小 iMax = i - 1; } else { // 达到要求,并且将边界条件列出来单独考虑 int maxLeft = 0; if (i == 0) { maxLeft = nums2[j-1]; } else if (j == 0) { maxLeft = nums1[i-1]; } else { maxLeft = Math.max(nums1[i-1], nums2[j-1]); } if ( (m + n) % 2 == 1 ) { return maxLeft; } // 奇数的话不需要考虑右半部分 int minRight = 0; if (i == m) { minRight = nums2[j]; } else if (j == n) { minRight = nums1[i]; } else { minRight = Math.min(nums2[j], nums1[i]); } return (maxLeft + minRight) / 2.0; //如果是偶数的话返回结果 } } return 0.0; }
•解法三
最激动人心的解法来了,我当时看到这个解法的时候,感叹连连,解法非常的精妙有容易理解,利用第K小数的思想,使用递归二分法进行解决。
具体思路,中位数其实就是第(总长度)/2小的数(奇偶我就不多说了,为了方便我就直接用奇数了),以为两个数组都是有序的,所以我们每次通过循环排除K的一半,直到最后找到K。看图看图,已这个例子为例,我们要找的K是7.
这个时候K/2等于3,然后我们比较两个数组的第三个位置上的数,就可以排除小的那一边的三个数一定不是第K小,然后我们这个时候将排除的数标记。
这个时候因为我们已经排除了3个数,接下来我们只要在新的两个数组中,找到K-3也就是第4小的数就可以了,同样的,将K比较K一半为止的数,重复如此
所以我们采用递归的思路,为了防止数组长度小于 k/2,所以每次比较 min(k/2,len(数组) 对应的数字,把小的那个对应的数组的数字排除,将两个新数组进入递归,并且 k 要减去排除的数字的个数。递归出口就是当 k=1 或者其中一个数字长度是 0 了。直接上代码。
private static int kMinNum(int start1, int end1, int[] nums1, int start2, int end2, int[] nums2, int k){ int len1 = end1 - start1 + 1; int len2 = end2 - start2 + 1; if(len1 > len2) return kMinNum(start2, end2, nums2, start1, end1, nums1, k); if(len1 == 0) return nums2[start2 + k - 1]; if(k == 1) return Math.min(nums1[start1], nums2[start2]); int i = start1 + Math.min(len1, k / 2) - 1; int j = start2 + Math.min(len2, k / 2) - 1; if(nums1[i] > nums2[j]){ return kMinNum(start1, end1, nums1, j + 1, end2, nums2,k - (j - start2 + 1)); }else{ return kMinNum(i + 1, end1, nums1, start2, end2, nums2, k - (i - start1 + 1)); } } public static double Test4S1(int[] nums1, int[] nums2) { int n = nums1.length; int m = nums2.length; int left = (n + m + 1) / 2; int right = (n + m + 2) / 2; return (kMinNum(0, n - 1, nums1, 0, m - 1, nums2, left) + kMinNum(0, n - 1, nums1, 0, m - 1, nums2, right)) * 0.5; }
•结束
第三种解法真的感觉相当的精妙,这种思路很值得去吃透理解。
-
找中位数O(n)算法
2015-07-21 10:09:29中位数是排序后数组的中间值,如果数组的个数是偶数个,则返回排序后数组的第N/2个数。 样例 给出数组[4, 5, 1, 2, 3], 返回 3 给出数组[7, 9, 4, 5],返回 5 解题思路: 利用快排划分的思想,递归...题目描述:
给定一个未排序的整数数组,找到其中位数。
中位数是排序后数组的中间值,如果数组的个数是偶数个,则返回排序后数组的第N/2个数。
样例
给出数组[4, 5, 1, 2, 3], 返回 3
给出数组[7, 9, 4, 5],返回 5
解题思路:
利用快排划分的思想,递归处理。
参考代码:
<span style="font-size:18px;">public class Solution { public int median(int[] nums) { return sub(nums, 0, nums.length - 1, (nums.length + 1) / 2); } private int sub(int[] nums, int start, int end, int size) { int mid = (start + end) / 2; int pivot = nums[mid]; int i = start - 1, j = end + 1; for (int k = start; k < j; k++) { if (nums[k] < pivot) { i++; int tmp = nums[i]; nums[i] = nums[k]; nums[k] = tmp; } else if (nums[k] > pivot) { j--; int tmp = nums[j]; nums[j] = nums[k]; nums[k] = tmp; k--; } } if (i - start + 1 >= size) { return sub(nums, start, i, size); } else if (j - start >= size) { return nums[j - 1]; } else { return sub(nums, j, end, size - (j - start)); } } }</span>
-
数组进行排序,时间复杂度O(N)&&求无序数组的中位数
2017-08-14 12:07:44求无序数组中位数,数组排序时间复杂度O(N)算法 排序知识回顾 -
关于中位数的时间复杂度为什么是O(n)
2016-07-24 22:31:43之所以,起“快速排序和寻找中位数”这个题目,并不是因为寻找中位数的时候使用了快速排序,而是这两个算法使用了一个同一个预处理结构 —— 划分,然后都是递归解决!中位数的也是根据一个数把原来的数划分一下,... -
Java实现 LeetCode 4 寻找两个有序数组的中位数
2020-02-11 18:54:06寻找两个有序数组的中位数 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n...则中位数是 2.0 示例 2: nums1 = [1, 2] nums2 = [3, 4... -
快速排序详解及不排序求中位数o(n)算法
2018-04-27 17:34:56中位数是指一段序列中,比它大的数和比它小的数的数量相等的那个数。序列经过排序后中位数在最中间。可以联想到使用快速排序的思想,找到最终位置在n/2的那个数。 而找中位数,是要找到最终位置在中间的那个... -
求两个有序序列的中位数。(要求时间复杂度为O(logN))
2017-10-04 01:17:03有序序列A0, A1…AN-1的中位数指A(N-1)/2的值,即第[(N+1)/2]个数(A0为第1个数)。 3.算法描述 总体思想:采用分治与递归策略,二分法每次将问题规模减半(约减半),然后对问题进行递归处理,在进行递归 -
求两个有序数组中的中位数和第k小的元素
2022-01-22 20:25:35接下来一行N个整数,表示arr1内的元素 再接下来一行N个整数,表示arr内的元素 输出一个整数表示答案 输入: 4 1 2 3 4 3 4 5 6 复制输出: 3 复制说明: 总共有8个数,上中位数是第4小的数,所以返回3。 输入: 3 0... -
求一个数阶乘的位数
2015-08-15 23:01:38求一个数阶乘的位数flyfish 2015-8-15例如 7!=5040 ,7的阶乘结果是4位数(10进制)求一个数的位数1 循环方法int get_digit_loop(int N) { int digit = 0; do { digit ++; } while ((N /= 10) > 0); return ... -
寻找两个有序数组的中位数
2019-02-17 13:13:06请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。 示例: A = [1, 3] B = [2] 则中位数是 2.0 A = [1, 2] B = [3, 4] 则中位数是 (2 + 3... -
任意输入一个正整数,判断这个数的位数
2019-01-04 09:17:58var int = parseInt(prompt("请输入一个正整数")); var count = 1; while(int>=10){ count++; int = int/10; } alert("这个数的位数是" + count); -
LeetCodeLeetCode 两个排序数组的中位数问题
2018-04-04 09:57:43请找出两个排序数组的中位数并且总的运行时间复杂度为 O(log (m+n)) 。 示例 1: nums1 = [1, 3] nums2 = [2] 中位数是 2.0 示例 2: nums1 = [1, 2] nums2 = [3, 4] 中位数是 (2 + 3)/2 = 2.5 这是问题,我刚... -
给定一个非负整数 num,反复将各个位上的数字相加,直到结果为一位数
2018-11-22 14:49:46示例: 输入: 38 输出: 2 解释: 各位相加的过程为:3...你可以不使用循环或者递归,且在 O(1) 时间复杂度内解决这个问题吗? class Solution { public int addDigits(int num) { if(num < 10){ ... -
LeetCode——寻找两个有序数组的中位数
2020-02-28 23:40:07题目: 给定两个大小为m和n的有序数组nums1和nums2。 请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为O(log(m+n))。 你可以假设nums1和nums2不会...则中位数是2.0 示例2: nums1=[1,2] nums2=[3,4... -
算法导论 9.3-7 O(n)时间求最接近中位数的k个数
2012-06-25 14:51:16step2:计算数组每个数与中位数差的绝对值,存于另一个数组B中O(n) step3:求出数组B中第k小的数ret O(n) step4:计算数组S中与ret差的绝对值小于ret的数并输出O(n) 其中,step4也可以通过划分的方法找出数组S中... -
C语言编程之取某整数的位数
2019-03-06 19:33:45(2)设置一个低4位全为1,其余全为0的数。可用~(~0<<4) (3)将上面二者进行&运算。 C程序源码: #include<stdio.h> int main() { unsigned a,b,c,d; scanf("%o",&... -
bfptr算法(即中位数的中位数算法)
2018-08-25 22:35:16BFPRT算法是解决从n个数中选择第k大或第k小的数这个经典问题的著名算法,但很多人并不了解其细节。本文将首先介绍求解这个第k小...将n个数排序(比如快速排序或归并排序),选取排序后的第k个数,时间复杂度为O(nlo... -
求无序数组的中位数(c语言版本)
2019-03-22 16:06:41在面试时,会经常被问道,如何求解一个无序数组的中位数?很多人往往都会第一感觉就是,先将该数组排序,然后找出最中间的那个数,但是这种思路通常的时间复杂度最好是O(nlogn),更糟的情况下会到O(n^2),并不是最优... -
获取一个数二进制序列中所有的偶数位和奇数位
2019-05-12 23:45:45获取一个数二进制序列中所有的偶数位和奇数位, 分别输出二进制序列。 用数字除以2的奇次方余下的数等于奇数位上的数字。 同理。偶数也是。 #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #... -
对数组排序时间复杂度要求O(n)与找中位数不能用排序
2017-08-06 17:32:42对数组排序时间复杂度要求O(n)思路 首先我们常规的排序都不能使用。所以我先遍历了一边数组,找到最小值和最大值。然后以它们的差值动态开辟了一段区间作为闭散列。然后再遍历了一边数组把相应元素的出现次数映射... -
【分治法】中位数问题,C++
2019-04-12 19:00:13采用分治法完成如下任务:...利用分治策略试设计一个O (log n)时间的算法求出这2n个数的中位数。 数据输入 由文件input.txt提供输入数据。文件的第1行中有1个正整数n(n<=200),表示每个数组有n个数。接下来的两... -
算法 - 有两个相同大小数组均已按升序排列,编程计算这两个数组的中位数(C++)
2019-02-26 10:41:50分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!请点击http://www.captainbed.net /* * Created by Chimomo * * Let X[0...n-1] and Y[0...n-1] be the two ... -
算法:寻找两个正序数组的中位数。
2020-07-07 14:10:25给定两个大小为 m 和 n 的正序(从小到大)数组nums1 和nums2。 请你找出这两个正序数组的中位数,并且要求算法的时间复杂度为O(log(m + n))。 -
用户从键盘输入一个1~99999之间的数,程序将判断这个数是几位数,并判断这个数是否是回文数
2019-03-21 23:39:37语法后生成一个完美的目录。 如何改变文本的样式 强调文本 强调文本 加粗文本 加粗文本 标记文本 删除文本 引用文本 H 2 O is是液体。 2 10 运算结果是 1024. 插入链接与图片 链接: ... -
bfprt算法,中位数的中位数算法,O(n)时间复杂度求解第k大数
2016-12-22 09:35:58// l-t的中位数的下标, 中位数是第 pos - l + 1数 bfprt(a,l,t,pos - l + 1 ); // 递归查找中位数的中位数,确保中位数在pos这个位置 // 4 将上一步得到的中位数作为划分的主元进行整个数组的划分, 快排思路... -
用js输入一个三位数字计算三位数字的和
2017-10-20 11:20:14Document var a = prompt("请输入一个三位数");... var b = a%10 //个位数字 var c = (a%100)/10 var d = Math.floor(c)//十位数字 var e = (a/100) var f = Math.floor(e)//百位数字 var g = b+d+f al -
为什么计算机中数字符号位0表示正数,1表示负数
2019-03-09 21:09:50只知道书本上说是有一个符号位,当该符号位为0时,表示的是正数,为1时表示负数。我那时没搞懂为什么这样规定,我觉得1么,代表正数挺合理的,那么0就自然表示负数咯,所以不解,只能死记硬背:0正1负。 我个人...