Skip to main content

输入集

David LiuNovember 22, 2024About 10 min

输入集

  • 排序数组
  • 山脉排序
  • 旋转排序

排序数组

以下题目均默认在非严格递增的数组上搜索，可以涵盖严格递增数组的情况。

（如果在非严格递减的数组上搜索，仅需把大于小于号取反，如>=变为<=，<=变为>=）

问题列表见右侧TOC目录：

在排序数组中查找数字

// in: nums[], target
int pos = searchMin(0, nums.length - 1, (mid) -> nums[mid] >= target);
return nums[pos] == target? pos: -1;

在排序数组中查找数字第一个位置

// in: nums[], target
int pos = searchMin(0, nums.length - 1, (mid) -> nums[mid] >= target);
return nums[pos] == target? pos: -1;

在排序数组中查找数字插入位置

查找数字插入位置，如果已经存在则返回位置

// in: nums[], target
// 不需要判断mid==nums.length的原因：searchMin中mid向下取整，mid永远不会等于末尾
return searchMin(0, nums.length, (mid) -> nums[mid] >= target);

题号：lc35

在排序数组中查找数字末一个位置

// in: nums[], target
int pos = searchMax(0, nums.length - 1, (mid) -> nums[mid] <= target);
return nums[pos] == target? pos: -1;

在排序数组中查找数字的范围

// in: nums[], target
int first = searchMin(0, nums.length - 1, (mid) -> nums[mid] >= target);
int last = searchMax(0, nums.length - 1, (mid) -> nums[mid] <= target);
return nums[first] != target? new int[]{-1, -1}: new int[]{first, last};

题号：lc34

在排序数组中查找数字的个数

// in: nums[], target
int first = searchMin(0, nums.length - 1, (mid) -> nums[mid] >= target);
int last = searchMax(0, nums.length - 1, (mid) -> nums[mid] <= target);
return nums[first] != target? 0: last - first + 1;

在排序矩阵中查找数字

// 排序矩阵，每一行从左往右递增，且下一行最小元素比上一行最大元素大
// 二维坐标转换一维坐标
// x, y -> x * m + y
// index -> x = index / m, y = index % m
boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 ||
        matrix[0] == null || matrix[0].length == 0) {
        return false;
    }
    int ans = searchMin(0, n * m - 1, (mid) -> get(matrix, mid) >= target)
    
    return get(matrix, ans) == target;
}

int get(int[][] matrix, int index) {
    int x = index / matrix[0].length;
    int y = index % matrix[0].length;
    return matrix[x][y];
}

转序数组

主要包括一些具有特殊排序性质的数组，如如下两种：

山脉数组

数组定义

山脉数组：如果数组 A 是一个山脉数组的话，那它满足如下条件：

首先，A.length >= 3

其次，在 0 < i < A.length - 1 条件下，存在 i 使得：

  • A[0] < A[1] < ... A[i-1] < A[i]
  • A[i] > A[i+1] > ... > A[A.length - 1]

不严格山脉数组，即所有的大于、小于均变为不严格的大于、小于

对于山脉数组，严格山脉数组和非严格的山脉数组都具有两段性（可以直接的判断在左右着右），如下提供一套统一的写法。

问题列表见右侧TOC目录：

山脉数组峰值

要求：找到一个山脉数组（可以是严格的也可以是不严格的）中峰值的索引

分析：即寻找第一个开始准备下降（比下一个元素大）的元素

public int peakIndexInMountainArray(int[] nums) {
    int n = nums.length;
    // 第一个符合mid > mid+1的，即第一个开始往下走的，即上坡的顶端
    return searchMin(0, n - 1, 
        (mid) -> nums[mid] > nums[mid + 1]
    );
}

题号：lc162, 852, lcr069

山脉数组搜索

要求：在山脉数组中寻找target的索引，如果不存在则返回-1

分析：先找到峰值的索引，然后左侧即为单调增的数组、右侧是单调减，然后分别在左右去搜索。由于target在左右两侧都有可能

int findInMountainArray(int target, MountainArray nums) {
    int n = nums.length();
    // 寻找峰值，第一个一个符合mid > mid+1的，即上坡的末尾，下面就准备下坡了
    int peak = searchMin(0, n - 1, 
        (mid) -> nums.get(mid) > nums.get(mid + 1)
    );
    // 搜索上坡
    int left = searchMin(0, peak, (mid) -> nums.get(mid) >= target);
    if (nums.get(left) == target) {
        return left;
    }
    // 搜索下坡
    int right = searchMin(peak, n - 1, (mid) -> nums.get(mid) <= target);
    if (nums.get(right) == target) {
        return right;
    }
    
    // 两边都没找到，则不存在
    return -1;
}

题号：1095

旋转排序数组

数组定义

原数组是单调递增/减的数组，然后经过未知步数k次的轮转（即末尾k个元素放到原数组的头部），形成旋转排序数组。

不严格旋转排序数组，即原数组变为不严格增/减

对于旋转排序数组，基本思路是判断在左侧（值大）还是右侧（值小）

  • 严格的直接具有两段性（可以直接的判断在左右着右），
  • 不严格的在最左侧和最右侧相等的时候，无法直接判断往左走还是往右走，所以对于不严格的旋转排序数组，需要恢复两段性：先遍历一遍消除最右侧与最左侧相同的元素，保证最右端的元素小于最左端（这样才可以判断左右）

问题列表见右侧TOC目录：

严格旋转排序数组的最小值

要求：找到一个严格旋转排序数组中最小值

分析：即寻找最靠左的比右边界小的元素（即找到的即未旋转部分的最开头的）

public int findMin(int[] nums) {
    int n = nums.length;
    // 即寻找最靠左的比有右边界小的元素
    int pos = searchMin(0, n - 1, (mid) -> nums[mid] <= nums[n - 1]);
    return nums[pos];
}

题号：lc153

严格旋转排序数组的最大值

要求：找到一个严格旋转排序数组中最大值

分析：即寻找最靠右的比左界小的元素（即找到的即旋转部分的最右侧）

public int findMax(int[] nums) {
    int n = nums.length;
    // 即寻找最靠右的比有左界小的元素
    int pos = searchMax(0, n - 1, (mid) -> nums[mid] >= nums[0]);
    return nums[pos];
}

题号：lc153

严格旋转排序数组搜索

要求：找到一个严格旋转排序数组中值为target的元素，如果不存在则返回-1

分析：即寻找最靠右的比左界小的元素（即找到的即旋转部分的最右侧）

两次遍历

推荐，结构思路清晰，条件简单

public int search(int[] nums, int target) {
    int n = nums.length;
    int max = searchMax(0, n - 1, (mid) -> nums[mid] >= nums[0]);
    if (target >= nums[0]) {
        int left = searchMax(0, max, (mid) -> nums[mid] <= target);
        return nums[left] == target? left: -1;
    }
    // searchMax 的时候开头元素不会被mid取到，如果后面条件都不符合才会返回头
    // 这里 max 是哨兵，可以防止越界(比如max+1==n了，search就直接返回n，nums[right]就越界了)
    int right = searchMax(max, n - 1, (mid) -> nums[mid] <= target);
    return nums[right] == target? right: -1;
}
一次遍历

不推荐，因为条件太复杂了，容易绕晕

public int search(int[] nums, int target) {
    int n = nums.length;
    // 即寻找最靠左的比有右界小的元素
    int pos = searchMin(0, n - 1, (mid) -> {
        if (nums[mid] < nums[n - 1]) { // 在右半部分
            // 若target > nums[n - 1]，则一定在左半侧，也需要往左找
            // 若mid大于等于target，则在最低点和mid之间，往左找；
            return target > nums[n - 1] || nums[mid] >= target;
        }
        // 在左半部分
        // target，在0和mid之间，则往mid左侧找
        return nums[0] <= target && target <= nums[mid]);
    });

    return nums[pos] == target? pos: -1;
}

题号：lc33

不严格旋转排序数组的最小值

与严格的类似，只是多了一步恢复两段性：

public int findMin(int[] nums) {
    int n = nums.length - 1;
    // 恢复两段性，保证最右端的元素小于最左端（这样才可以判断左右）
    while (0 < end && nums[end] == nums[0]) n--;
    int end = n;
    int pos = searchMin(0, end, (mid) -> nums[mid] <= nums[end]);
    return nums[pos];
}

题号：lc154

不严格旋转排序数组的最大值

与严格的类似，只是多了一步恢复两段性：

public int findMax(int[] nums) {
    int n = nums.length - 1;
    // 恢复两段性，保证最右端的元素小于最左端（这样才可以判断左右）
    while (n > 0 && nums[n] == nums[0]) n--;
    int pos = searchMax(0, n, (mid) -> nums[mid] >= nums[0]);
    return nums[pos];
}
public int findMax(int[] nums) {
    int left = 0, right = nums.length - 1;
    // 恢复两段性，保证最右端的元素小于最左端（这样才可以判断左右）
    while (left < right && nums[right] == nums[left]) right--;
    int pos = searchMax(left, right, (mid) -> nums[mid] >= nums[0]);
    return nums[pos];
}

题号：字节笔试题，无lc原题

不严格旋转排序数组搜索

与严格的类似，只是多了一步恢复两段性：

public boolean search(int[] nums, int target) {
    int n = nums.length - 1;
    // 恢复两段性
    while (n > 0 && nums[n] == nums[0]) n--;
    int max = searchMax(0, n, (mid) -> nums[mid] >= nums[0]);
    int left = searchMax(0, max, (mid) -> nums[mid] <= target);
    if (nums[left] == target) {
        return true;
    }
    // 这里max相当于哨兵，可以防止越界
    // （searchMax的时候开头元素不会被mid取到，如果后面条件都不符合才会返回头）
    int right = searchMax(max, n, (mid) -> nums[mid] <= target);
    return nums[right] == target;
}

题号：lc88

特殊

隔板法，两个有序数组的中位数

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int n = nums1.length, m = nums2.length;
    if (n > m) {
        return findMedianSortedArrays(nums2, nums1);
    }

    int i = searchMax(0, n, (mid) -> {
        int j = (n + m + 1) / 2 - mid;
        return nums1[mid - 1] <= nums2[j];
    });

    int j = (n + m + 1) / 2 - i;
    int left1 = i == 0? Integer.MIN_VALUE: nums1[i - 1];
    int left2 = j == 0? Integer.MIN_VALUE: nums2[j - 1];
    double median1 = Math.max(left1, left2);
    if ((n + m) % 2 == 1) {
        return median1;
    }

    int right1 = i == n? Integer.MAX_VALUE: nums1[i];
    int right2 = j == m? Integer.MAX_VALUE: nums2[j];
    double median2 = Math.min(right1, right2);
    return (median1 + median2) / 2;
}
David's Blog
Copyright © 2025 David Liu