1172. 寻找第k大数
时间: 2023-10-30 14:22:35 浏览: 76
根据引用,给出一个数组,找出数组的第k大的数的方法是基于快速排序的思路。具体步骤如下:
1. 定义一个函数`quickFind`,参数为数组`arr`、左边界`left`、右边界`right`和要找的第k大的数`k`。
2. 在函数内部,使用快速排序的思路进行处理。首先选择一个基准值`key`,将其设为数组的第一个元素`arr[left]`。
3. 使用两个指针`i`和`j`,分别指向数组的左边界和右边界。
4. 在一个循环中,将比基准值大的元素移到数组的右边,比基准值小的元素移到数组的左边。
5. 循环结束后,将基准值放到合适的位置,使得基准值的左边都是比其小的数,右边都是比其大的数。
6. 根据基准值的位置和k的关系,判断第k大的数在基准值的左边还是右边。
- 若基准值所在的位置右边的数据小于k-1个,说明第k大的数在基准值的左边序列中,需要对左边的数据进行快排,并找到第k-big-1大的数据。
- 若基准值所在的位置右边的数据大于k-1个,说明第k大的数在基准值的右边序列中,需要对右边的数据进行快排并找到第k大的数。
- 若基准值所在的位置右边的数据正好是k-1个,说明基准值就是第k大的数,返回基准值。
7. 在主函数中调用`quickFind`函数,给出数组和要找的第k大的数。
根据引用和引用中的代码实现,给定一个整数数组a和要找的第K大的数,可以使用快速排序的原理来寻找第K大的数。具体步骤如下:
1. 定义一个函数`quickSort`,参数为数组`arr`、起始位置`start`、结束位置`end`和要找的第K大的数`k`。
2. 在函数内部,设置递归结束条件,若起始位置大于结束位置,则返回-1。
3. 设置两个指针`i`和`j`,分别指向起始位置和结束位置,以及一个基准值`base`,将其设为数组的起始位置的元素`arr[start]`。
4. 在一个循环中,将比基准值大的元素移到数组的右边,比基准值小的元素移到数组的左边。
5. 循环结束后,将基准值放到合适的位置,使得基准值的左边都是比其小的数,右边都是比其大的数。
6. 根据基准值的位置和k的关系,判断第k大的数在基准值的左边还是右边。
- 若基准值的位置等于`arr.length - k`,说明找到了第K大的数,返回该值。
- 若基准值的位置小于`arr.length - k`,说明第K大的数在基准值的右边序列中,继续递归调用`quickSort`函数,在右边序列中寻找第K大的数。
- 若基准值的位置大于`arr.length - k`,说明第K大的数在基准值的左边序列中,继续递归调用`quickSort`函数,在左边序列中寻找第K大的数。
7. 在主函数中调用`quickSort`函数,给出数组、起始位置、结束位置和要找的第K大的数。
综上所述,根据以上的方法和步骤,可以找到数组的第K大的数。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* [C++——寻找第k大的数](https://blog.csdn.net/ldm_666/article/details/117229499)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
- *2* *3* [寻找数组中第k大的数](https://blog.csdn.net/m0_37671741/article/details/108304136)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)