LeetCode747.至少是其他数字两倍的最大数：「快速排序」&「归并排序」&「堆排序」

浏览次数 : 次 2022-01-13

博文字数统计 : 2.4k字 | 阅读所需时长 : 10分

× 文章目录

1. LeetCode747.至少是其他数字两倍的最大数：「快速排序」&「归并排序」&「堆排序」

LeetCode747：至少是其他数字两倍的最大数
- 时间：2022-01-13
- 力扣难度：Easy
- 个人难度：Easy
- 数据结构：数组
- 算法：模拟、排序

LeetCode747.至少是其他数字两倍的最大数：「快速排序」&「归并排序」&「堆排序」

1. 题目描述

题目：原题链接
- 给你一个整数数组 nums ，其中总是存在唯一的一个最大整
- 请你找出数组中的最大元素并检查它是否至少是数组中每个其他数字的两倍。
- 如果是，则返回最大元素的下标，否则返回 -1
输入输出规范
- 输入：整数数组nums
- 输出：最大数的索引
输入输出示例
- 输入：[3,6,1,0]
- 输出：1

2. 方法：简单模拟

思路
- 本题要求数组中的最大值是否比任意一个元素的两倍都要大，最直接的思路就是一次遍历找到最大值，再一次遍历比较是否比两倍还大
- 实际上，只要最大数比次大数的两倍大，就一定比其他元素的两倍大，因此可以优化成一次遍历
- 值得注意的是：本题输入的数组只有一个元素时，默认返回0即可，即满足最大数比其他的两倍大
复杂度分析：n 是数组的长度
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$

题解：直接模拟

public int dominantIndex(int[] nums) {
       if(nums == null || nums.length == 0) return -1;
       int n = nums.length;
       if(n == 1) return 0;
       int max = nums[0];
       int secondMax = Integer.MIN_VALUE;
       int index = 0;
       for(int i = 1; i < n; i++) {
           if(nums[i] >= max){
               secondMax = max;
               max = nums[i];
               index = i;
           }else if(nums[i] >= secondMax) secondMax = nums[i];
       }
       // System.out.print(1 >= 0 << 1);
       return max >= secondMax << 1 ? index : -1;
}

3. 扩展：排序算法

本题非常简单，因此我们可以扩展一下程序员基本技能：排序算法
- 十大排序算法：冒泡、快排、插入、选择、归并排序、堆排序、希尔排序、基数排序、计数排序、桶排序
- 排序的对象：数组、链表等
冒泡 & 选择 & 插入
- 作为最简单的三种排序(都属于比较排序)，这里简单讲一下三者的特点与区别，以升序为例
- 冒泡排序：进行 n 轮，每轮逐个对比元素大小，将大的元素后移，即每一轮会将最大元素移到数组末尾，同时数组局部也发生排序
- 选择排序：进行 n 轮，每轮通过比较，寻找最大的元素，记录其索引，将其与末尾元素交换，同样是每一轮会将最大元素移到数组末尾，但是数组局部不会发生改变
- 插入排序：进行 n 轮，每轮取出未排序的一个元素(按顺序)，然后比较其与前面以及排好序的元素，找到其要插入的位置并插入，不会取找到最大最小元素，数组局部不会发生改变
- 此外，本文主要介绍最常见、使用最广泛的几种排序：快排、归并、堆排序

快速排序：QuickSort：partition & sort

思想：分治
- 提前设置一个基准，在每轮排序时通过该基准将序列分成两部分，大于基准的和小于基准的各自在一边
- 以此达到二分的效果，最终分成的多段序列都各自有序
- 基准可以取序列中任意一个元素，如开头、中间、结尾
复杂度
- 时间复杂度：$O(nlogn)$，最坏情况下$O(n^2)$
- 空间复杂度：$O(logn)$，主要是递归函数的栈空间
- 排序不稳定，性能受输入数据的影响，因此需要优化
快排优化：随机乱序避免二分失效
- 实际上，由于快排对序列的分布要求较高，即最坏情况下会退化回$O(n^2)$的时间复杂度
- 所以针对难搞的数据集，要先对数据随机乱序，再取基准进行快排。

源码：取开头为基准，双向遍历

public class QuickSorter {
    private static Random random = new Random();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strings = br.readLine().split(" ");
        int[] nums = new int[strings.length];
        for (int i = 0; i < strings.length; i++) {
            nums[i] = Integer.parseInt(strings[i]);
        }
        new QuickSorter().quickSort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }

    private void quickSort(int[] nums, int l, int r) {
        if (l < r) {
            int idx = partition(nums, l, r);
            quickSort(nums, l, idx - 1);
            quickSort(nums, idx + 1, r);
        }
    }

    private int partition(int[] nums, int l, int r) {
        int idx = random.nextInt(r - l) + l;
        swap(nums, l, idx);
        int pivot = nums[l];
        while (l < r) {
            while (l < r && nums[r] >= pivot) --r;
            nums[l] = nums[r];
            while (l < r && nums[l] <= pivot) ++l;
            nums[r] = nums[l];
        }
        nums[l] = pivot; // 注意交换基准元素和边界元素
        return l;
    }

    private void swap(int[] nums, int i, int j) {
        // 位运算
        nums[i] = nums[i] ^ nums[j] ^ (nums[j] = nums[i]);
        // int temp = nums[i];
        // nums[i] = nums[j];
        // nums[j] = temp;
    }
}

源码：取开头为基准，单向遍历

private int partition(int[] nums, int l, int r) {
    int idx = random.nextInt(r - l) + l;
    swap(nums, l, idx);
    int pivot = nums[l];
    int mark = l;
    for (int i = l + 1; i <= r; i++) {
        if(nums[i] < pivot) {
            mark++;
            swap(nums, mark, i);
        }
    }
    swap(nums, l , mark); // 注意交换基准元素和边界元素
    return mark;
}

归并排序：MergeSort：divide & merge

思想：分治、多路归并(多叉树)
- 归并排序也是通过分治的思想，将序列不断分解为多个子序列，然后再进行排序，各个子序列有序后，合并得到的就是有序序列
- 一般的情况下都是用二路归并，即类似二分的方式从序列中点来分解、合并序列，而一些大文件排序的场景，可能会用到多路归并
- 与快排不同的是，快排在按照基准partition分区的过程中，也会进行一定的排序(大的一边、小的一边)，而归并排序是完全将序列划分到不可分时才进行排序
复杂度分析
- 时间复杂度：$O(nlogn)$，合并的复杂度为$O(n)$，而分治的过程是一个完全二叉树，深度为$O(logn)$，两者嵌套，总的复杂度$O(nlogn)$
- 空间复杂度：$O(n)$，需要一个辅助数组
- 排序稳定，性能不受输入数据的影响

源码

public class MergeSorterArray {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strings = br.readLine().split(" ");
        int[] nums = new int[strings.length];
        for (int i = 0; i < strings.length; i++) {
            nums[i] = Integer.parseInt(strings[i]); // 7354613
        }
        new MergeSorterArray().mergeSort(nums, 0, nums.length - 1, new int[nums.length]);
        System.out.println(Arrays.toString(nums));
    }


    public void mergeSort(int[] nums, int left, int right, int[] save) {
        if (left < right) {
            int mid = (right - left) / 2 + left;
            mergeSort(nums, left, mid, save);
            mergeSort(nums, mid + 1, right, save);
            merge(nums, left, mid, right, save);
        }
    }

    private void merge(int[] nums, int left, int mid, int right, int[] save) {
        int i = left, j = mid + 1; // 双指针，用来合并数组
        int index = 0;
        while (i <= mid && j <= right) {
            if (nums[i] < nums[j]) {
                save[index++] = nums[i++];
            } else {
                save[index++] = nums[j++];
            }
        }
        while (i <= mid) {
            save[index++] = nums[i++];
        }
        while (j <= right) {
            save[index++] = nums[j++];
        }
        // 将排序后的辅助数组copy回原数组
        index = 0;
        while (left <= right) {
            nums[left++] = save[index++];
        }
    }
}

堆排序：HeapSort

思想：最小堆的构建与调整
- 堆排序是一种选择排序，是利用完全二叉树的性质来优化排序的一种算法
- 主要分为构建初始堆、交换堆顶和末尾元素、重建堆三个方面
- 其中，要注意完全二叉树的叶子节点的特性，以及重建堆的时候有一半的树无需操作
- 值得注意的是，堆排序无需真的实现树结构，只需要用数组模拟小顶堆即可
复杂度分析
- 时间复杂度：$O(nlogn)$，构建初始堆的复杂度为$O(n)$，而重建堆的复杂度为$O(nlogn)$，两者平行，总的复杂度$O(nlogn)$
- 空间复杂度：$O(1)$，无需额外空间
- 排序不稳定，性能不受输入数据的影响

源码

public class HeapSorter {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strings = br.readLine().split(" ");
        int[] nums = new int[strings.length];
        for (int i = 0; i < strings.length; i++) {
            nums[i] = Integer.parseInt(strings[i]); // 7354613
        }
        new HeapSorter().heapSort(nums, nums.length);
        System.out.println(Arrays.toString(nums));
    }

    public void heapSort(int[] nums, int n) {
        buildHeap(nums, n);
        for (int i = n - 1; i >= 0; i--) {
            swap(nums, i, 0); // 交换堆顶和末尾的元素，最大值
            heapify(nums, i, 0); // 从根节点开始调整整个树
        }
    }

    // 创建大顶堆
    private void buildHeap(int[] nums, int n) {
        int lastIndex = n - 1;
        int parentIndex = (lastIndex - 1) / 2;
        for (int i = parentIndex; i >= 0; i--) {
            heapify(nums, n, i);
        }
        System.out.println(Arrays.toString(nums));
    }

    private void heapify(int[] nums, int n, int i) {
        if (i >= n) return;
        int left = 2 * i + 1, right = 2 * i + 2; // 左子节点和后子节点的索引
        int max = i; // 最大元素的索引，初始化为目前要调整的子树的根节点
        // 比较交换局部最大值
        if (left < n && nums[left] > nums[max]) max = left;
        if (right < n && nums[right] > nums[max]) max = right;
        if (max != i) { // 如果max变化了
            swap(nums, i, max);
            heapify(nums, n, max); // 继续取调整节点值被提升到 i 节点后，新的需要调整的子树
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

本文作者： Chthollists
发布时间： 2022-01-13 10:15:33
最后更新： 2022-01-21 23:09:05
本文标题： LeetCode747.至少是其他数字两倍的最大数：「快速排序」&「归并排序」&「堆排序」
本文链接： https://chthollists.github.io/post/107ec78.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！