10数据结构与算法刷题之【排序算法】篇

简介: 10数据结构与算法刷题之【排序算法】篇

牛客网


寻找第K大【中等】


题目链接:寻找第K大


题目内容:有一个整数数组,请你根据快速排序的思路,找出数组中第 k 大的数。给定一个整数数组 a ,同时给定它的大小n和要找的 k ,请返回第 k 大的数(包括重复的元素,不用去重),保证答案存在。


最佳思路:快排+二分+随机基准点。在快排的过程中不断的找到对应的基准点,然后以这个基准点比较k(基准点的左边是>该基准点的,这样我们才能将基准点的索引与第k大的索引来进行比较)


思路:快排+二分+随机基准点


复杂度分析:


时间复杂度:O(n.logn)

空间复杂度:O(n)

一个探索思路的过程:


import java.util.*;
public class Solution {
    private static int res;
    Private static Random random = new Ramdom();
    public int findKth(int[] a, int n, int K) {
        quickSort(a, 0, n - 1, K);
        return res;
    }
    public void quickSort(int[] a, int l, int r, int K) {
        if (l > r) {
            return;
        }
        int mid = partition(a, l, r);
        //看这个基准点与K的位置是否相符
        if (mid + 1 == K) {
            res = a[mid];
        }else if (mid + 1 < K) {
            quickSort(a, mid + 1, r, K);
        }else {
            quickSort(a, 0, mid - 1, K);
        }
    }
    public int partition(int[] a, int l, int r) {
        int x = Math.abs(random.nextInt()) % (r - l + 1) + l;
        swap(a, l, x);
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if (a[i] >= a[l]) {
                j++;
                swap(a, i, j);
            }
        }
        //交换基准点
        swap(a, l, j);
        return j;
    }
    public void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}



不同的分块思路:


//方式一:
public int partition(int[] a, int l, int r) {
    int x = Math.abs(random.nextInt()) % (r - l + 1) + l;
    swap(a, l, x);
    int j = l;
    for (int i = l + 1; i <= r; i++) {
        if (a[i] >= a[l]) {
            j++;
            swap(a, i, j);
        }
    }
    //交换基准点
    swap(a, l, j);
    return j;
}
//方式二:
public int partition(int[] a, int l, int r) {
    int v = a[l];
    int i = l + 1;
    int j = r;
    while (true) {
        //目标找到小于基准值的
        while (i <= r && a[i] > v ) {
            i++;
        }
        //目标找到大于基准值的
        //注意:这里j>=l+1
        while (j >= l + 1 && a[j] < v) {
            j--;
        }
        if (i > j) {
            break;
        }
        swap(a, i, j);
        i++;
        j--;
    }
    //交换基准点
    swap(a, l, j);
    return j;
}


相关文章
|
12天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
46 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
15天前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
17 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
8天前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
23 4
|
15天前
|
搜索推荐 算法
数据结构与算法学习十四:常用排序算法总结和对比
关于常用排序算法的总结和对比,包括稳定性、内排序、外排序、时间复杂度和空间复杂度等术语的解释。
13 0
数据结构与算法学习十四:常用排序算法总结和对比
|
13天前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
8 0
|
15天前
|
机器学习/深度学习 搜索推荐 算法
探索数据结构:初入算法之经典排序算法
探索数据结构:初入算法之经典排序算法
|
15天前
|
算法 Java 索引
数据结构与算法学习十五:常用查找算法介绍,线性排序、二分查找(折半查找)算法、差值查找算法、斐波那契(黄金分割法)查找算法
四种常用的查找算法:顺序查找、二分查找(折半查找)、插值查找和斐波那契查找,并提供了Java语言的实现代码和测试结果。
14 0
|
15天前
|
存储 缓存 分布式计算
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
这篇文章是关于数据结构与算法的学习指南,涵盖了数据结构的分类、数据结构与算法的关系、实际编程中遇到的问题以及几个经典的算法面试题。
24 0
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
|
19天前
|
机器学习/深度学习 存储 算法
【数据结构与算法基础】——算法复杂度
【数据结构与算法基础】——算法复杂度
|
5月前
|
算法 C++ Python
数据结构与算法===贪心算法
数据结构与算法===贪心算法