自学内容网 自学内容网

从LeetCode215看排序算法

目录

LeetCode215 数组的第K个最大元素

 ① 第一反应:java的内置排序Arrays.sort()

② 冒泡排序

③归并排序(先分解再合并)

④快速排序(边分解边排序)

⑤堆排序


LeetCode215 数组的第K个最大元素

给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。

请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

 ① 第一反应:java的内置排序Arrays.sort()

arrays.sort的复杂度取决于所使用的排序算法。在java中,Arays类中的sort方法使用的是一种优化的快速排序算法或归并排序算法
对于快速排席算法,其平均时间复杂度为0(nl0gn),其中n是数组的大小。然而,在最坏情况下,快速排序的时间复杂度可以达到O(n^2),这发生在数组已经有序的情况下。
对于归并排序算法,其时间复杂度始终为0(nlog n),不论输入数据的情况如何。
总结起来,Arrays.sort方法的平均时间复杂度为0(nlog n),最坏情况下可能为O(n^2)。


② 冒泡排序

思路:总结来说就是两个for循环。多次遍历数组,每次遍历通过不断比较相邻元素的大小,如果左边大于右边就交换元素顺序,最终会将一个最大(或最小的)元素冒泡到数组的末尾或开头。直到最终没有任何元素需要交换(end一直--)。

举个例子,假设我们有一组数字:3, 38, 5, 44, 15, 47, 36, 26, 27, 2, 46, 4, 19, 50, 48。

下面是冒泡排序的执行过程:
1.第一轮比较后,最大的数字 50 被冒泡到了数组末尾,数组变为:3, 5, 38, 15, 44, 36, 26, 27, 2, 46, 4, 19, 47, 48, 50

2.第二轮比较后,第二大的数字 48 被冒泡到了倒数第二的位置,数组变为:3, 5, 15, 38, 36, 26, 27, 2, 44, 4, 19, 46, 47, 48, 50

3.经过多轮比较和交换后,所有数字按照从小到大的顺序排列完成。

第k大只要找到第k个泡泡即可,无需向后比较对整个数组进行排序

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return bubbleSort(nums, k);
    }

    int bubbleSort(int[] nums, int k){
        int n = nums.length;
        int count = 0;
        for(int i=0;i<n-1;i++){
            for(int j=0;j<n-i-1;j++){
                if(nums[j] > nums[j+1]){
                    int tmp =nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = tmp;
                }
            }
            count++;
            if(count == k){
                break;
            }
        }
        return nums[n-k];
    }
}

时间复杂度:最坏情况:O(N^2)
      最好情况:O(N)
空间复杂度:O(1)
 


③归并排序(先分解再合并)

思路:通过分治法将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。与快速排序相比,快速排序是将序列划分成两个子序列,再递归使子序列有序;而归并排序是先使子序列有序,再进行合并。

运算符小妙用:

偶数&1 结果为0;奇数&1 结果为1;

左移相当于乘以2^n;右移相当于除以2^n,所以通常会用>>1来代替除以2。

不用第三个变量交换两个整数:

    void swap(int x , int y)
    {
         x ^= y;
         y ^= x;
         x ^= y;
    }

不断从中间划分子数组,递归合并

public class MergeSort {   
    public static int[] mergeSort(int[] nums, int l, int h) {
        if (l == h)
            return new int[] { nums[l] };
         
        int mid = l + (h - l) / 2;
        int[] leftArr = mergeSort(nums, l, mid); //左有序数组
        int[] rightArr = mergeSort(nums, mid + 1, h); //右有序数组
        int[] newNum = new int[leftArr.length + rightArr.length]; //新有序数组
         
        int m = 0, i = 0, j = 0; 
        while (i < leftArr.length && j < rightArr.length) {
            newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
        }
        while (i < leftArr.length)
            newNum[m++] = leftArr[i++];
        while (j < rightArr.length)
            newNum[m++] = rightArr[j++];
        return newNum;
    }

 LeetCode 4:寻找两个正序数组的中位数

这道题就用到了归并排序

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
 
        int totalLength = nums1.length + nums2.length;
        int[] nums = new int[totalLength];
        int i = 0, j = 0;
        int index = 0;
        while (index <= totalLength /2) {
            if (i < nums1.length && (j >= nums2.length || nums1[i] < nums2[j])) {
                nums[index] = nums1[i++];
            } else{
                nums[index] = nums2[j++];
            }
            if (index == totalLength / 2) {
                //nums数组长度为偶数
                if ((totalLength & 1) == 0) {
                    return (nums[index] + nums[index - 1]) / 2.0;
                } else {
                    //nums数组长度是奇数
                    return 1.0 * nums[index];
                }
            }
            index++;
        }
        return 0.0;
    }
}

时间复杂度:O(nlogn)(稳定,因为每次都是从中间划分)

空间复杂度:递归造成栈空间的使用,最好O(nlogn),最坏O(n)


④快速排序(边分解边排序)

思路:通过分治法将一个数组分成较小的子数组,然后递归地对每个子数组进行排序。

移动左右指针,左指针向右移动,直到找到一个大于等于分界值的元素;右指针向左移动,直到找到一个小于等于分界值的元素。交换这两个元素的位置,然后再次移动左右指针,直到左指针和右指针指向同一个元素,再递归左右子数组。

快速排序找到第k个最大的,就是排序后递增子数组的倒数第k个(序号为n-k)

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        return quickSelect(nums, 0, n-1, n-k);
    }

    public int quickSelect(int[] nums, int l, int r, int k){
        if(l == r)  return nums[k];
        int x = nums[l], i = l-1, j = r+1;
        while(i < j){
            do i++;  while(nums[i] < x);
            do j--;  while(nums[j] > x);
            if(i < j){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }
        //这个时候i==j==x,要寻找的坐标<=j则说明第k大元素在分界元素左边
        if(k <= j)  return quickSelect(nums, l, j, k);
        else return quickSelect(nums, j+1, r, k);
    }
}

快排的时间复杂度我们可以认为是O(nlogn),但当遇到原数组本身有序的情况下,其时间复杂度就会退化至O(n^2),这个其实很好理解,举个例子就明白了:

最优情况下,即每趟选择key时都恰好选择到数组的中间值时(第n层可以确定2^{n-1}个数字位置),快排的时间复杂度如下图完全(满)二叉树:


在最坏的情况下,这个树是一个完全的斜树,只有左半边或者右半边,即每趟选择key时都恰好选择到数组最大或最小的值时(即每一层都只能确定一个数字位置)。这时候我们的比较次数就变为∑n−1i=1(n−i)=(n−1)+(n−2)+⋯+1=n∗(n−1)2=O(n^2)

时间复杂度:最好O(nlogn),最坏O(n^2)

空间复杂度:递归造成栈空间的使用,最好O(nlogn),最坏O(n)


⑤堆排序

java提供了PriorityQueue,可以构建小顶堆

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(); //小顶堆
        for(int num : nums){
            queue.add(num);
            if(queue.size() > k){
                queue.poll();
            }
        }
        return queue.peek();
    }
}

自己构建堆 

class Solution {
    public int findKthLargest(int[] nums, int k) {
        //-------------1.首先,构建最大堆[6,5,4,3,2,1]----------------
        //建大堆:要从堆的最后一个非叶子节点开始向下调整
        for (int i = nums.length/2-1; i >= 0; i--) {
            adjustHeap(nums,i,nums.length);
        }
        //---2.每次把最大的换到最后一个位置,调整堆,交换后不把最后一个数看作堆里的数据-------
        for(int i = nums.length-1;i >= nums.length-k ;i--){
            swap(nums,0,i);
            adjustHeap(nums,0,i);    //选出次小的数
        }
        return nums[nums.length-k];
    }
        //向下调整算法
        public static void adjustHeap(int[] nums,int node,int tail){
        int left = node*2+1;
        int right = node*2+2;
        //-------------大的往上浮,小的往下浮--------------------
        int max = node;
        if(left<tail&&nums[left]>nums[max]){
            max=left;
        }
        if(right<tail&&nums[right]>nums[max]){
            max=right;
        }
        //---------max是父节点和左右子节点中最大的数-------------------
        //max!=node证明左右子节点有比父节点大的数,需要进行交换
        if(max!=node){
            swap(nums,max,node);
            adjustHeap(nums,max,tail);
        }
    }
 
    public static void swap(int[] nums, int index1, int index2){
        int tmp = nums[index1];
        nums[index1]=nums[index2];
        nums[index2]=tmp;
    }
}


原文地址:https://blog.csdn.net/weixin_43562105/article/details/140348056

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!