首页 > 程序开发 > 软件开发 > 其他 > 正文
LintCode 中位数
2017-06-19       个评论    来源:  
收藏    我要投稿

LintCode 中位数

1.描述

给定一个未排序的整数数组,找到其中位数。

中位数是排序后数组的中间值,如果数组的个数是偶数个,则返回排序后数组的第N/2个数。

2.分析

首先对着干数组进行快速排序,之后返回中间值即可。

3.代码

class Solution {

public:

/**

* @param nums: A list of integers.

* @return: An integer denotes the middle number of the array.

*/

int Partition(vector& nums,int first,int end)

{

int i=first;

int j=end;

int t;

while(i {

while(i if(i {

t=nums[i];

nums[i]=nums[j];

nums[j]=t;

i++;

}

while(i if(i {

t=nums[j];

nums[j]=nums[i];

nums[i]=t;

j--;

}

}

return i;

}

void QuickSort(vector& nums,int first,int end)

{

if(first {

int pivot=Partition(nums,first,end);

QuickSort(nums,first,pivot-1);

QuickSort(nums,pivot+1,end);

}

}

int median(vector &nums) {

// write your code here

QuickSort(nums,0,nums.size()-1);

/*for(int i=0;i {

cout< }*/

return nums[((nums.size()+1)/2)-1];

}

};

4.总结

这里注意中间的数为(length+1)/2,考虑到是在数组中因此实际位置为(length+1)/2-1.

点击复制链接 与好友分享!回本站首页
上一篇:LintCode 整数排序 II
下一篇:delphi 入门之《动态创建菜单》
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 |
版权所有: 88bifa.com--致力于做实用的IT技术学习网站