LeetCode 面试题 16.16. 部分排序

Categories:

题目描述
思路分析
1. 解法一：双向扫描（推荐）
相似题目

题目描述

✅ 面试题 16.16. 部分排序

思路分析

解法一：双向扫描（推荐）

核心思路：

从左到右维护最大值，若当前值小于最大值，则该位置一定在待排序区间内。

从右到左维护最小值，若当前值大于最小值，则该位置一定在待排序区间内。

结合两次扫描得到最短需排序的子数组区间。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public int[] subSort(int[] array) {
        int n = array.length;
        int left = -1;
        int right = -1;

        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            if (array[i] < max) {
                right = i;
            } else {
                max = array[i];
            }
        }

        int min = Integer.MAX_VALUE;
        for (int i = n - 1; i >= 0; i--) {
            if (array[i] > min) {
                left = i;
            } else {
                min = array[i];
            }
        }

        return new int[]{left, right};
    }
}

func subSort(array []int) []int {
	left, right := -1, -1

	maxVal := -1 << 60
	for i := 0; i < len(array); i++ {
		if array[i] < maxVal {
			right = i
		} else {
			maxVal = array[i]
		}
	}

	minVal := 1 << 60
	for i := len(array) - 1; i >= 0; i-- {
		if array[i] > minVal {
			left = i
		} else {
			minVal = array[i]
		}
	}

	return []int{left, right}
}

相似题目

题目	难度	考察点
581. 最短无序连续子数组	中等	双向扫描
75. 颜色分类	中等	原地排序
769. 最多能完成排序的块	中等	前缀最大值
768. 最多能完成排序的块 II	困难	单调性质
283. 移动零	简单	双指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/68408313