Median详解编程语言
寻找未排序数组的中位数,简单粗暴的方法是先排序后输出中位数索引处的数,但是基于比较的排序算法的时间复杂度为 O(nlogn), 不符合题目要求。线性时间复杂度的排序算法常见有计数排序、桶排序和基数排序,这三种排序方法的空间复杂度均较高,且依赖于输入数据特征(数据分布在有限的区间内),用在这里并不是比较好的解法。
由于这里仅需要找出中位数,即找出数组中前半个长度的较大的数,不需要进行完整的排序,说到这你是不是想到了快速排序了呢?快排的核心思想就是以基准为界将原数组划分为左小右大两个部分,用在这十分合适。快排的实现见 Quick Sort, 由于调用一次快排后基准元素的最终位置是知道的,故递归的终止条件即为当基准元素的位置(索引)满足中位数的条件时(左半部分长度为原数组长度一半)即返回最终结果。由于函数原型中左右最小索引并不总是原数组的最小最大,故需要引入相对位置(长度)也作为其中之一的参数。若左半部分长度偏大,则下一次递归排除右半部分,反之则排除左半部分。
C++:
class Solution { public: /** * @param nums: A list of integers. * @return: An integer denotes the middle number of the array. int median(vector int nums) { if (nums.empty()) return 0; int len = nums.size(); return helper(nums, 0, len - 1, (len + 1) / 2); private: int helper(vector int nums, int l, int u, int size) { // if (l = u) return nums[u]; int m = l; // index m to track pivot for (int i = l + 1; i ++i) { if (nums[i] nums[l]) { ++m; int temp = nums[i]; nums[i] = nums[m]; nums[m] = temp; // swap with the pivot int temp = nums[m]; nums[m] = nums[l]; nums[l] = temp; if (m - l + 1 == size) { return nums[m]; } else if (m - l + 1 size) { return helper(nums, l, m - 1, size); } else { return helper(nums, m + 1, u, size - (m - l + 1)); };
JAVA:
public class Solution { /** * @param nums: A list of integers. * @return: An integer denotes the middle number of the array. public int median(int[] nums) { if (nums == null) return -1; return helper(nums, 0, nums.length - 1, (nums.length + 1) / 2); // l: lower, u: upper, m: median private int helper(int[] nums, int l, int u, int size) { if (l = u) return nums[u]; int m = l; for (int i = l + 1; i i++) { if (nums[i] nums[l]) { m++; int temp = nums[m]; nums[m] = nums[i]; nums[i] = temp; // swap between array[m] and array[l] // put pivot in the mid int temp = nums[m]; nums[m] = nums[l]; nums[l] = temp; if (m - l + 1 == size) { return nums[m]; } else if (m - l + 1 size) { return helper(nums, l, m - 1, size); } else { return helper(nums, m + 1, u, size - (m - l + 1)); }
以相对距离(长度)进行理解,递归终止步的条件一直保持不变(比较左半部分的长度)。
以题目中给出的样例进行分析,size 传入的值可为(len(nums) + 1) / 2, 终止条件为m - l + 1 == size, 含义为基准元素到索引为l的元素之间(左半部分)的长度(含)与(len(nums) + 1) / 2相等。若m - l + 1 size, 即左半部分长度偏大,此时递归终止条件并未变化,因为l的值在下一次递归调用时并未改变,所以仍保持为size; 若m - l + 1 size, 左半部分长度偏小,下一次递归调用右半部分,由于此时左半部分的索引值已变化,故size应改为下一次在右半部分数组中的终止条件size - (m - l + 1), 含义为原长度size减去左半部分数组的长度m - l + 1.
复杂度分析和快排类似,这里也有最好情况与最坏情况,平均情况下,索引m每次都处于中央位置,即每次递归后需要遍历的数组元素个数减半,故总的时间复杂度为 O(n(1+1/2+1/4+ ))=O(2n)O(n (1 + 1/2 + 1/4 + )) = O(2n)O(n(1+1/2+1/4+ ))=O(2n), 最坏情况下为平方。使用了临时变量,空间复杂度为 O(1), 满足题目要求。
原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/20661.html
cjava相关文章
- Go 编程语言的真正优势是什么?
- python登录pop3邮件服务器接收邮件详解编程语言
- python开发简单socket程序在两台电脑之间传输消息详解编程语言
- Javascript监测网络状况详解编程语言
- 判断输入的参数是否是一个合格的身份证号码详解编程语言
- spring的AOP简介与事务传播特性总结详解编程语言
- python模块之psutil详解编程语言
- javaScript之jQuery框架详解编程语言
- Akka(17): Stream:数据流基础组件-Source,Flow,Sink简介详解编程语言
- Html学习笔记详解编程语言
- JS中的prototype详解编程语言
- EasyUI DataGrid 多级表头设置详解编程语言
- Java中ArrayList类的用法详解编程语言
- Spring+Mybatis+Maven+MySql搭建实例详解编程语言
- 通过 Apache Commons HttpClient 发送 HTTPS 请求详解编程语言
- springMVC拦截器和过滤器总结详解编程语言
- 重磅:Spring Boot 2.0 正式发布!详解编程语言
- JedisConnectionException: java.net.SocketException: Socket closed;Unknown reply: ; It seems like server has closed the connection.解决办法详解编程语言
- Python3 判断文件和文件夹是否存在、创建文件夹详解编程语言
- C++中Cstring使用小结详解编程语言
- ABAP ALV可编辑字段长度受限详解编程语言
- 自开发程序加权限控制(SU21创建权限对象、PFCG创建Role)详解编程语言
- SAP query传输以后需要重新生成程序详解编程语言
- leetcode(4) Median of Two Sorted Arrays详解编程语言
- python之类之多继承详解编程语言