算法笔记-快速排序之无序数组中查找中位数
程序员文章站
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.
推荐阅读