找出数组[1...n]中第k小元素

古城微笑少年丶 2022-01-08 02:15 252阅读 0赞

1 //问题描述： 试编写一个算法，使之能够在数组L[1...n]中找出第k小的元素(即从小到大排序后处于第k个位置的元素)
     2 
     3 #include <stdio.h>
     4 
     5 // 结合快排思想，查找第5小函数
     6 int find_the_minist_k(int sz[], int k, int low, int high)
     7 {
     8     int lowtemp = low, hightemp = high; // 由于下面修改low, high并且下面递归会用到low, high
     9     int pivot = sz[low];
    10     while (low < high)
    11     {
    12         while (low < high && sz[high] >= pivot)
    13             high--;
    14         sz[low] = sz[high];
    15         while (low < high && sz[low] <= pivot)
    16             low++;
    17         sz[high] = sz[low];
    18     }
    19     sz[low] = pivot;
    20     // 上面即为快排的划分算法
    21     if (low == k) // 由于与k相同，直接返回pivot元素
    22         return sz[low];
    23     else if (low > k) //枢轴值大于k，在前一部分表中递归查找
    24         return find_the_minist_k(sz, k, lowtemp, low - 1);
    25     else // 枢轴值小于k，在后一部分中递归查找，注意，查找的k应为k减去前一部分表长度
    26         return find_the_minist_k(sz, k - low, low + 1, hightemp);
    27 }
    28 int main()
    29 {
    30     int a[] = {
        0, 5, 10, 8, 100, 50, -10, 60};
    31     // 查找数组a中第3小的元素,数组长度为8
    32     int the_k_number = find_the_minist_k(a, 3, 0, 7);
    33     printf("%d\n", the_k_number);
    34     return 0;
    35 }

转载于:https://www.cnblogs.com/sqdtss/p/10739168.html

发表评论取消回复

表情：

评论列表（有 0 条评论，252人围观）

还没有评论，来说两句吧...

相关阅读

相关找出数组中第k大的数

package com.threeTop.www; /** * 找出数组中第k大的数 * @author wjgs ...

╰半夏微凉°/ 2024年04月17日 14:47/ 0 赞/ 57 阅读

相关快排找出第K大的数（C++实现）

算法实现： include <stdio.h> void printAll(int a[], int n){ int

蔚落/ 2024年03月16日 14:46/ 0 赞/ 45 阅读

相关 N29_输入n个整数，找出其中最小的K个数。

package new_offer; import java.util.ArrayList; import com.sun.net.

偏执的太偏执、/ 2023年08月17日 17:36/ 0 赞/ 139 阅读

相关找出数组中的第K大的数或者第K小的数

class Solution { public: int findKthLargest(vector<int>& res, int k)

本是古典何须时尚/ 2022年12月31日 01:25/ 0 赞/ 171 阅读

相关 leetcode 1545. 找出第 N 个二进制字符串中的第 K 位

给你两个正整数 n 和 k，二进制字符串 Sn 的形成规则如下： S1 = "0" 当 i > 1 时，Si = Si-1 + "1" + rev

╰+攻爆jí腚メ/ 2022年11月27日 03:07/ 0 赞/ 145 阅读

相关线性时间选择第K小元素（随机化选择第K小元素）C++

// 随机化产生第K小数.cpp : Defines the entry point for the console application. // \include "

布满荆棘的人生/ 2022年05月15日 12:59/ 0 赞/ 162 阅读

相关线性时间选择第K小元素（随机化选择第K小元素）C++

// 随机化产生第K小数.cpp : Defines the entry point for the console application. // \include "

àì夳堔傛蜴生んèń/ 2022年05月15日 12:58/ 0 赞/ 166 阅读

相关找出第k个最小的元素

/\ \题目：编写程序，从数组x\[0...n-1\]中找出第k个最小的元素。算法可以对x中的元素进行排序 \/ \include<stdio.h> \inclu

电玩女神/ 2022年04月11日 14:25/ 0 赞/ 189 阅读

相关找出数组[1...n]中第k小元素

1 //问题描述：试编写一个算法，使之能够在数组L[1...n]中找出第k小的元素(即从小到大排序后处于第k个位置的元素) 2 3 includ

古城微笑少年丶/ 2022年01月08日 02:15/ 0 赞/ 253 阅读

相关对数组中的每一个元素，找出他后面第几个数比自己大

给定一个列表`[73, 74, 75, 71, 69, 72, 76, 73]`，输出应该是 `[1, 1, 4, 2, 1, 1, 0, 0]` public

红太狼/ 2021年11月09日 16:36/ 0 赞/ 246 阅读