Lintcode-中位数

问题描述:

给定一个未排序的整数数组,找到其中位数。
中位数是排序后数组的中间值,如果数组的个数是偶数个,则返回排序后数组的第N/2个数。

思路一:

可以使用快速排序将数组排好序,然后返回中位数,这样做的时间复杂度是O(nlogn).

思路二:

为了降低复杂度,现在我们使用“折半的快速排序”。就是每一次只对一边的数组进行排序。

示例代码:
#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: An integer denotes the middle number of the array.
     */
    int Qsort(vector<int>&nums,int low,int high)//这里需要用引用
    {
        int i=low;
        int j=high;
        //int key=nums[0];
    //刚开始快速排序我一直是这么写的,然后一直AC不了。
//但是只测试快排又是可以运行出结果的,所以我一直以为是median函数里出错了。
//一直调试了很久很久,几个小时。所以这件事情也让我明白了基础扎实是很重要的。
        int key=nums[low];
        while (i<j)
        {
            while (i<j&&nums[j]>=key)
            {
                j--;
            }
            swap(nums[i],nums[j]);
            while (i<j&&nums[i]<=key)
            {
                i++;
            }
            swap(nums[i],nums[j]);
        }
        //nums[i]=key;
        return i;
    }

    int median(vector<int> &nums) {
        // write your code here
        int n=nums.size();
        int key=0,k=0;
        int left=0,right=n-1;
        if(n%2==0) key=n/2-1;
        else
        {
            key=n/2;
        }
        k=Qsort(nums,0,n-1);
        while (k!=key)
        {
            if(k<key)
            {
                left=k+1;
                k=Qsort(nums,left,right);
            }
            else
            {
                right=k-1;
                k=Qsort(nums,left,right);
            }
        } 
        return nums[key];
    }
};

注意点1:

int Qsort(vector<int>&nums,int low,int high)//这里需要用引用
    {
        int i=low;
        int j=high;
        //int key=nums[0];
               ....
         }

刚开始快速排序我一直是这么写的,然后一直AC不了。但是只测试快排又是可以运行出结果的,所以我一直以为是median函数里出错了。一直调试了很久很久,几个小时。所以这件事情也让我明白了基础扎实是很重要的。

注意点2:

int key=0,k=0;
        int left=0,right=n-1;
        if(n%2==0) key=n/2-1;
        else
        {
            key=n/2;
        }
        k=Qsort(nums,0,n-1);
        while (k!=key)
        {
            if(k<key)
            {
                left=k+1;
                k=Qsort(nums,left,right);
            }
            else
            {
                right=k-1;
                k=Qsort(nums,left,right);
            }
        } 

while循环里的left和right怎么控制,以及每次Qsort的上下限也要注意。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 给定一个未排序的整数数组,找到其中位数。中位数是排序后数组的中间值,如果数组的个数是偶数个,则返回排序后数组的第N...
    DayDayUpppppp阅读 467评论 0 0
  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,779评论 0 33
  • 概述:排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    每天刷两次牙阅读 3,747评论 0 15
  • 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    蚁前阅读 5,223评论 0 52
  • 在我的记忆里,能够明显感觉到父母特别的关心的两个时期就是中考以及高考。那段时间,我就像家里一个易碎的花瓶,一直被父...
    孙泰明阅读 290评论 0 0