欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法笔记-快速排序之无序数组中查找中位数

程序员文章站 2022-06-17 19:50:06
...
问题描述:

给一个无序数组array和数组长度n,找出其中的中位数(这里考虑n为奇数)

Sample:

 ***** Input:
 ***** @[@(500),@(120),@(7),@(220),@(3),@(8),@(4),@(200),@(100)
 ***** Output:
 ***** 100
解法一:将数组进行排序,然后输出array(n-1)/2,排序算法中我们选取快速排序:
- (void)quickSortingWitharray:(NSMutableArray *)array andleftIndex:(NSInteger)left withRightIndex:(NSInteger)right{

    if (left >= right) {
        return;
    }

    NSInteger leftIndex = left;
    NSInteger rightIndex = right;
    NSInteger key = [array[left] integerValue];

    while (leftIndex < rightIndex) {

        while ([array[rightIndex] integerValue] >= key && leftIndex < rightIndex) {
            rightIndex --;
        }
        array[leftIndex] = array[rightIndex];


        while ([array[leftIndex] integerValue] <= key && leftIndex < rightIndex) {
            leftIndex ++;
        }
        array[rightIndex] = array[leftIndex];
    }

    array[leftIndex] = @(key);

    [self quickSortingWitharray:array andleftIndex:left withRightIndex:leftIndex - 1];
    [self quickSortingWitharray:array andleftIndex:leftIndex + 1 withRightIndex:right];


}

解法二:还是用快速排序,但是我们可以减少一部分排序,因为每次快排都是将数组分成左右两个小数组再进行排序,我们知道右边的数组中的值都是大于左边数组中的值,而且我们可以获取到每次分组时的位置index,index和(n-1)/2,做比较,当相等时,array[index]就找到了我们要的值

- (NSInteger)yquickSortingWitharray:(NSMutableArray *)array andleftIndex:(NSInteger)left withRightIndex:(NSInteger)right{

    NSInteger leftIndex = left;
    NSInteger rightIndex = right;
    NSInteger key = [array[left] integerValue];

    while (leftIndex < rightIndex) {

        while ([array[rightIndex] integerValue] >= key && leftIndex < rightIndex) {
            rightIndex --;
        }
        array[leftIndex] = array[rightIndex];


        while ([array[leftIndex] integerValue] <= key && leftIndex < rightIndex) {
            leftIndex ++;
        }
        array[rightIndex] = array[leftIndex];
    }

    array[leftIndex] = @(key);

    return leftIndex;


}

- (NSInteger)finmidArray:(NSMutableArray *)array {
    NSInteger mid = (array.count-1)/2;
    NSInteger start = 0;
    NSInteger end = array.count - 1;

    NSInteger index = [self yquickSortingWitharray:array andleftIndex:start withRightIndex:end];
    while (index != mid) {
        if (mid < index) {
            index = [self yquickSortingWitharray:array andleftIndex:start withRightIndex:index - 1];
        } else {
            index = [self yquickSortingWitharray:array andleftIndex:index + 1 withRightIndex:end];
        }
    }

    return [array[index] integerValue];
}
  • 通过下图我们可以看到通过解法二,可以省略很多次排序也可以拿到中位数100.
    算法笔记-快速排序之无序数组中查找中位数

上一篇: 分发饼干

下一篇: 罗马数字转整数