精华内容
下载资源
问答
  • 无序数组的中位数

    2019-04-22 11:32:00
    无序数组的中位数不能使用排序算法,而且要求时间复杂度O(n)。# -*- coding: utf-8 -*-​# @Time : 2019/4/22 10:42 AM# @Author : George# @File : main7.py# @Contact : georgewang1994@163.com​​def heapify...

    无序数组的中位数

    不能使用排序算法,而且要求时间复杂度O(n)。

    # -*- coding: utf-8 -*-

    # @Time   : 2019/4/22 10:42 AM
    # @Author : George
    # @File   : main7.py
    # @Contact : georgewang1994@163.com


    def heapify(seq, start, end):
       """
      找出从start到end的范围内的最小值,放在堆顶的位置
      :param seq:
      :param start:
      :param end:
      :return:
      """
       # start结点的左右子结点
       left, right = 2 * start + 1, 2 * (start + 1)
       mi = start
       # 从左右子结点中选出最小值
       if left < end and seq[mi] > seq[left]:
           mi = left
       if right < end and seq[mi] > seq[right]:
           mi = right
       if mi != start:
           # 找到最小值后调整位置
           seq[start], seq[mi] = seq[mi], seq[start]
           heapify(seq, mi, end)


    def find_mid_num(nums):
       heap_num = len(nums)//2
       heap = nums[:heap_num+1]

       # 建立最小堆
       start, end = len(heap) // 2 - 1, len(heap)
       for i in range(len(heap)//2-1, -1, -1):   # 前n/2个元素建堆
           heapify(heap, i, end)

       # 将原数组后面一般的数据一一和堆顶进行比较,大于堆顶则替换掉
       # 原理就是替换掉一般的数值,剩下的堆顶就是中位数
       for j in range(heap_num + 1, len(nums)):
           if nums[j] > heap[0]:
               # 堆顶被替换掉
               print '堆顶%s被替换成%s' % (heap[0], nums[j])
               heap[0] = nums[j]
               heapify(heap, 0, end)

       # 奇数时是最中间的数,偶数时是最中间两数的均值
       return heap[0] if len(nums) % 2 else (heap[0] + min(heap[1], heap[2])) / 2.0

    转载于:https://www.cnblogs.com/George1994/p/10749180.html

    展开全文
  • 求一个无序数组的中位数中位数是将数组排序之后,数组个数为奇数时,取中间的即为中位数;数组个数为偶数时,取中间两个的平均值即为中位数。思路一:要取得中位数,即给数组排序,使用任意排序算法均可,然后按数组...

    求一个无序数组的中位数

    中位数是将数组排序之后,数组个数为奇数时,取中间的即为中位数;数组个数为偶数时,取中间两个的平均值即为中位数。

    思路一:

    要取得中位数,即给数组排序,使用任意排序算法均可,然后按数组下标取其中位数。

    PS:该方法很直观,此处不实现

    思路二:

    1.设数组元素为n个,且为奇数个时,取数组前(n+1)/2个元素建一个小堆

    2.遍历数组剩余元素,如果比堆顶元素大即入堆,如果比堆顶元素小或等于堆顶元素,即舍弃,不入堆

    3.遍历完数组元素时,堆顶即为中位数

    PS:此处要使用STL中的优先级队列,博主需要见缝插针的介绍一下优先级队列

    优先级队列:

    优先队列不遵循队列先进先出的规则,而是根据队列中元素的优先权,优先权最大的先被取出。

    优先级队列使用方法:

    头文件:   #include

    声明方式:

    1.普通声明:

    priority_queue  tty;

    这个是使用STL里默认的排列顺序,即从大到小排列,建大堆

    2.自定义优先级:

    struct compare

    {

    bool operator()(int x, int y)

    {

    return x > y; //x,小的优先级高

    }

    };

    代码实现:

    #include

    #include

    #include

    #include

    #include

    using namespace std;

    struct compare

    {

    bool operator()(int x, int y)

    {

    return x > y;   //x,小的优先级高

    }

    };

    void HeapSort(int* arr, int len)

    {

    assert(arr);

    int newlen = (len + 1) / 2;     //用数组的一半多1长度建堆

    priority_queue, compare> tty;    //建小堆

    for (int i = 0; i < newlen;i++)

    {

    tty.push(arr[i]);

    }

    //此时数组中一半+1的元素已经建成小堆,需要比较数组后面元素

    for (int j = newlen; j < len; ++j)

    {

    //拿数组后半部分依次和堆顶比较,大于堆顶时入堆

    if (arr[j]>tty.top())

    {

    tty.pop();    //要保持堆内元素个数不变

    tty.push(arr[j]);

    }

    }

    if (!tty.empty())

    {

    cout <

    }

    cout << endl;

    }

    void TestHeapSort()

    {

    int arr[] = { 58, 99, 66, 34, 21, 2, 0, 8, 7, 6, 5, 222222, 111, 888, 3 };

    int len = sizeof(arr) / sizeof(arr[0]);

    HeapSort(arr, len);

    }

    int main()

    {

    TestHeapSort();

    system("pause");

    return 0;

    }

    579e437ca69dca5d5b79501f0f0307ea.png

    展开全文
  • 找出一个无序数组的中位数

    万次阅读 热门讨论 2017-08-04 14:01:25
    找出一个无序数组的中位数

    要解决这个问题首先要了解什仫是中位数,所谓的中位数就是在一组有序的数字中找到中间的那个数字。如果数字的个数是奇数则直接返回中间的那个数,如果数字的个数是偶数此时这组数据的中位数有两个,取中间两个数的平均值即可。
    想法一、不论用什仫排序算法使得该组数据有序,直接取中间值即可。
    这种只要你掌握常见的排序算法就可以了,在这里就不实现了。
    想法二、利用快排的思想
    1、先进行一趟快排,使得div左边的值都比arr[div]小,div右边的值都比arr[div]大,但是这个div的位置是不确定的,可能位于中间,也可能偏左或者偏右。
    2、计算出mid所在的下标,如果是奇数则是mid=(size+1)/2,如果是偶数则是mid=size/2。
    3、此时需要比较mid和div所在的位置。如果mid在div所在位置的左边,此时就要递归去左半区间查找;如果mid在div的右边,此时就要递归去右半区间查找;如果恰好相等则说明div/mid所在的位置就是中位数。
    代码实现如下:

    int PartSort(int *arr, int start, int end)
    {
        int left = start;
        int right = end;
        int key = arr[end];   //选取关键字
        while (left < right)
        {
            while (left < right && arr[left] <= key)  //左边找比key大的值
            {
                ++left;
            }
            while (left < right && arr[right] >= key)  //右边找比key小的值
            {
                --right;
            }
            if (left < right)
            {
                swap(arr[left], arr[right]);  //找到之后交换左右的值
            }
        }
        swap(arr[right], arr[end]);
        return left;
    }
    //求一个无序数组的中位数
    int GetMidNumNoSort1(int *arr,int size)
    {
        assert(arr);
        int start = 0;
        int end = size - 1;
        int mid = (size - 1) / 2;
        int div = PartSort(arr,start,end);
        while (div != mid)
        {
            if (mid < div)   //左半区间找
                div = PartSort(arr, start, div - 1);
            else    //左半区间找
                div = PartSort(arr, div + 1, end);
        }
        return arr[mid];   //找到了
    }

    想法三、建堆的思想

    1、如果数组元素的个数是奇数,取数组前(size+1)/2个元素建堆,如果是偶数则取前 size/2 个元素建堆。
    2、建完堆之后,此时堆顶的元素是这前 (size-1)/2 个元素中最小的;此时需要将数组中剩余的元素分别和堆顶的元素进行比较:如果小于等于堆顶元素则直接丢弃,如果大于堆顶的元素则需要更新堆顶的元素并重新调整堆的结构,使其保证小顶堆的特性。
    3、将剩余的元素全部比较完之后,此时堆顶的元素就是所要求的中位数。
    在这里需要提到的是,优先级队列的底层也是通过建堆来实现的。默认是建大堆,此时就要编写一个使其建小堆的仿函数了,其实也就是相当于修改了它的优先级。
    代码实现如下:

    //建小堆来实现
    #include<queue>
    #include<vector>
    int GetMidNumNoSort2(int *arr, int size)
    {
        assert(arr);
        int len = (size + 1) / 2;   //奇数个元素
        //int len = size / 2;
        struct Compare    //建小堆
        {
            int operator()(int left, int right)
            {
                return left > right;
            }
        };
        priority_queue<int, vector<int>, Compare> heap;
        //先以整个数组的前len个元素建小堆
        for (int i = 0; i < len; i++)
        {
            heap.push(arr[i]);
        }
        for (int i = len; i < size; i++)
        {
            if (arr[i] > heap.top())  //比堆顶元素大则更新该小堆
            {
                heap.pop();
                heap.push(arr[i]);
            }
        }
        if (!heap.empty())
        {
            return heap.top();
        }
    }

    在这里就分享结束了,以上仅是我个人的想法,也通过了奇数数组个数和偶数数组个数的测试,不喜勿喷!!!

    展开全文
  • 无序数组的中位数

    千次阅读 2018-10-02 21:35:01
    无序数组的中位数,我们首先想到的是将该数组进行排序,然后找到中间的元素,但是往往面试的时候,面试官就会怼你,说你时间复杂度太高了....要你优化(个人感觉,面试官对你问了问题,有一个自己的标准,如果你答...

    求无序数组的中位数,我们首先想到的是将该数组进行排序,然后找到中间的元素,但是往往面试的时候,面试官就会怼你,说你时间复杂度太高了....要你优化(个人感觉,面试官对你问了问题,有一个自己的标准,如果你答不到他的点子上,他就不满意,各种怼,直到你想到他的标准,否则,挂掉),针对上面的问题,用一下两种方法求解

     

    1 先排序后取中间值:

    注意:python 3里面的运算符:"//":取整  "/" :真除法   "~":按位取反运算符:对数据的每个二进制位取反,即把1变为0,把0变为1 。~x类似于 -x-1

    def get_middle(array):
        array.sort()
        index = len(array)//2
        return (array[index]+array[~index])/2
    
    print(get_middle([2,1,5,8,3,9,4]))
    print(get_middle([2,1,5,8,3,9,4,6]))

    2 通过构建最小堆来求解

    思想是:

    1 对无序数组的前len(array)//2长度的元素建立最小堆,这样就得到了一个堆顶元素小于任意一个堆里的元素

    2 将剩下的一半元素依次与堆顶元素比较。若比堆顶元素大,则替换之,并调整堆。(也就是说:依次遍历剩下一般的元素,与当前的堆顶元素作比较,如果大于堆顶元素,则替换,这时,重新调整堆的结构,使其保持为最小堆,否则,遍历下一个元素,知道剩下的一半元素遍历结束)

    3 数组剩下的所有元素比较完后,可以输出中位数。数组长度为奇数时,输出堆顶元素即可。数组长度为偶数时,输出堆顶元素与它的孩子结点中较小的那个的均值。

    def heap_adjust(parent,heap):   #更新结点后进行调整
        child=2*parent+1
        while len(heap)>child:
            if child+1<len(heap) and heap[child+1]<heap[child]:
                child+=1
            if heap[parent]<=heap[child]:
                break
            heap[parent],heap[child]=heap[child],heap[parent]
            parent,child=child,child*2+1
     
    def find(nums):
        k=len(nums)//2 +1
        heap=nums[:k]
        for i in range(k,-1,-1):   #前n/2个元素建堆
            heap_adjust(i,heap)
        for j in range(k,len(nums)):
            if nums[j]>heap[0]:
                heap[0]=nums[j]
                heap_adjust(0,heap)
        #奇数时是最中间的数,偶数时是最中间两数的均值
        return heap[0] if len(nums)%2==1 else float(heap[0]+min(heap[1],heap[2]))/2
     
    print(find([1,2,8,9,3,5,4,6,7,0]))
    print(find([1,3,2,4])

    展开全文
  • 题目:求一个无序数组的中位数。 如:{2,5,4,9,3,6,8,7,1}的中位数为5,{2,5,4,9,3,6,8,7,1,0}的中位数为4和5。 要求:不能使用排序,时间复杂度尽可能高 提示:考虑堆或者快排思想解决。
  • 求一个无序数组的中位数

    千次阅读 2017-08-03 17:33:07
    求一个无序数组的中位数 中位数是将数组排序之后,数组个数为奇数时,取中间的即为中位数;数组个数为偶数时,取中间两个的平均值即为中位数。 思路一: 要取得中位数,即给数组排序,使用任意排序算法均可,然后按...
  • 无序数组的中位数(c语言版本)

    千次阅读 2019-03-22 16:06:41
    在面试时,会经常被问道,如何求解一个无序数组的中位数?很多人往往都会第一感觉就是,先将该数组排序,然后找出最中间的那个数,但是这种思路通常的时间复杂度最好是O(nlogn),更糟的情况下会到O(n^2),并不是最优...
  • 和求无序数组的中位数。 例题: 1 . int a[] = { 12, 13, 12, 13, 19, 18, 15, 12, 15, 16, 17 },要求对数组a进行排序,要求时间复杂度为O(N) 2.求一个无序数组的中位数。 如:{ 2, 5, 4, 9, 3, 6, 8, 7, 1 }的中...
  • 求一个无序数组的中位数

    千次阅读 2017-08-04 23:13:05
    问题描述求一个无序数组的中位数。 如:{2,5,4,9,3,6,8,7,1}的中位数为5,{2,5,4,9,3,6,8,7,1,0}的中位数为4和5。 要求:不能使用排序,时间复杂度尽可能低。 提示:考虑堆或者快排思想解决方法1:堆思路1: 分析...
  • 1.算法题一:无序数组的中位数 (快排思想O(N) 时间复杂度) package com.lightsword.leetcodeproblems import org.junit.jupiter.api.Test import java.util.* /** * 1.算法题一:无序数组的中位数 (快排思想O(N) ...
  • 对有限数组进行计数排序和求一个无序数组的中位数——题集(十九) 今天分享一下,实现对有限数组进行计数排序和求一个无序数组的中位数的代码实现和测试用例。 数组定义为:int a[] = {12,13,12,13,19,18,15,12,15,...
  • 思路: 1、快排思想 2、小顶堆或者大顶堆(使用优先级队列PriorityQueue实现小顶堆) 3、top k问题可采用类似解法。 代码: package com.my.test.datastructure.array;... * 无序数组的中位数 ...
  • 无序数组的中位数 中位数即是排过序后的处于数组最中间的元素。 不考虑数组长度为偶数的情况。设集合元素个数为n。 简单的想了下: 思路1) 把无序数组排好序,取出中间的元素  时间复杂度 采用普通的比较...
  • O(n)时间实现求出一个无序数组的中位数;下面是我联想多数派问题的误区,详细正确的解答慢慢想下。
  • 算法要求:输入一个整数数组,求出本数组的中位数。 思路1:将数组排序,然后直接从排序数组中找出中位数。时间复杂度取决于排序算法,最快是快速排序,O(nlogn),或者是非比较的基数排序,时间为O(n),空间为O...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 386
精华内容 154
关键字:

无序数组的中位数