跳转至

4101. Find All Numbers Disappeared in an Array III 🔒

难度中等

题目描述

You are given an integer array nums and two integers lower and upper.

An integer is missing if it lies in the inclusive range [lower, upper] and does not appear in nums.

Return a 2D integer array representing all missing integers grouped into contiguous ranges. Represent each range as [start, end], including both endpoints, and return the ranges in increasing order of start.

Consecutive missing integers must belong to the same range. If there are no missing integers, return an empty array.

 

Example 1:

Input: nums = [3,9,7], lower = 1, upper = 12

Output: [[1,2],[4,6],[8,8],[10,12]]

Explanation:

  • The missing integers are [1, 2, 4, 5, 6, 8, 10, 11, 12].
  • Grouping the missing integers into the minimum number of contiguous ranges, we get [1, 2], [4, 6], [8, 8], and [10, 12].
  • Therefore, the answer is [[1, 2], [4, 6], [8, 8], [10, 12]].

Example 2:

Input: nums = [1,1,1000000000], lower = 5, upper = 1000000000

Output: [[5,999999999]]

Explanation:

  • The value 1 lies outside [lower, upper], so it does not cover any integer in the range.
  • The only integer of the range that appears in nums is 1000000000.
  • Every integer from 5 to 999999999 is missing, and they are consecutive, so they form the single range [5, 999999999].

Example 3:

Input: nums = [2,3,5], lower = 2, upper = 3

Output: []

Explanation:

  • Both 2 and 3 appear in nums, so there are no missing integers.
  • Therefore, the answer is [].

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= lower <= upper <= 109

解法

方法一：排序 + 二分查找

思考

区间 \([\textit{lower}, \textit{upper}]\) 的上界高达 \(10^9\)，逐个检查区间内的整数是否出现在 \(\textit{nums}\) 中会直接超时。

数组长度最多为 \(10^5\)，真正把 \([\textit{lower}, \textit{upper}]\) 切开的只有落在这一范围内的数组元素。将 \(\textit{nums}\) 排序后，可以用二分查找定位出落入 \([\textit{lower}, \textit{upper}]\) 的下标区间 \([l, r)\)，相邻元素之间的空隙就是一段连续的缺失整数。

用 \(\textit{pre}\) 表示当前待覆盖的最小整数（初始为 \(\textit{lower}\)），依次遍历下标区间 \([l, r)\) 内的元素 \(\textit{cur}\)：若 \(\textit{pre} < \textit{cur}\)，则 \([\textit{pre}, \textit{cur} - 1]\) 为一段缺失区间，随后将 \(\textit{pre}\) 推进到 \(\textit{cur} + 1\)，最后再补上末尾可能剩余的 \([\textit{pre}, \textit{upper}]\)。

我们先将数组 \(\textit{nums}\) 升序排序，然后通过二分查找找到第一个大于等于 \(\textit{lower}\) 的下标 \(l\)，以及第一个大于等于 \(\textit{upper} + 1\) 的下标 \(r\)。此时下标区间 \([l, r)\) 内的元素即为 \(\textit{nums}\) 中所有落在 \([\textit{lower}, \textit{upper}]\) 范围内的数。

我们用变量 \(\textit{pre}\) 记录当前尚未被覆盖的最小整数，初始时 \(\textit{pre} = \textit{lower}\)。遍历 \(i \in [l, r)\)，设当前元素为 \(\textit{cur} = \textit{nums}[i]\)：

  • 若 \(\textit{pre} < \textit{cur}\)，说明区间 \([\textit{pre}, \textit{cur} - 1]\) 内的整数均未出现，将其加入答案数组 \(\textit{ans}\)；
  • 随后更新 \(\textit{pre} = \textit{cur} + 1\)（若存在重复元素，此时 \(\textit{pre} > \textit{cur}\) 会自然跳过）。

遍历结束后，若仍有 \(\textit{pre} \le \textit{upper}\)，说明末尾区间 \([\textit{pre}, \textit{upper}]\) 内的整数也缺失，将其加入答案数组 \(\textit{ans}\)。最后返回 \(\textit{ans}\) 即可。

时间复杂度 \(O(n \log n)\)，空间复杂度 \(O(\log n)\)。其中 \(n\) 是数组 \(\textit{nums}\) 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def findDisappearedNumbers(
        self, nums: list[int], lower: int, upper: int
    ) -> list[list[int]]:
        nums.sort()
        l = bisect_left(nums, lower)
        r = bisect_left(nums, upper + 1)
        ans = []
        pre = lower
        for i in range(l, r):
            cur = nums[i]
            if pre < cur:
                ans.append([pre, cur - 1])
            pre = cur + 1
        if pre <= upper:
            ans.append([pre, upper])
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int[][] findDisappearedNumbers(int[] nums, int lower, int upper) {
        Arrays.sort(nums);
        int l = lowerBound(nums, lower);
        int r = lowerBound(nums, upper + 1);
        List<int[]> ans = new ArrayList<>();
        int pre = lower;
        for (int i = l; i < r; i++) {
            int cur = nums[i];
            if (pre < cur) {
                ans.add(new int[] {pre, cur - 1});
            }
            pre = cur + 1;
        }
        if (pre <= upper) {
            ans.add(new int[] {pre, upper});
        }
        return ans.toArray(new int[ans.size()][]);
    }

    private int lowerBound(int[] nums, int target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> findDisappearedNumbers(vector<int>& nums, int lower, int upper) {
        sort(nums.begin(), nums.end());
        int l = lower_bound(nums.begin(), nums.end(), lower) - nums.begin();
        int r = lower_bound(nums.begin(), nums.end(), upper + 1) - nums.begin();
        vector<vector<int>> ans;
        int pre = lower;
        for (int i = l; i < r; i++) {
            int cur = nums[i];
            if (pre < cur) {
                ans.push_back({pre, cur - 1});
            }
            pre = cur + 1;
        }
        if (pre <= upper) {
            ans.push_back({pre, upper});
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func findDisappearedNumbers(nums []int, lower int, upper int) [][]int {
    sort.Ints(nums)
    l := sort.SearchInts(nums, lower)
    r := sort.Search(len(nums), func(i int) bool {
        return nums[i] > upper
    })
    ans := [][]int{}
    pre := lower
    for i := l; i < r; i++ {
        cur := nums[i]
        if pre < cur {
            ans = append(ans, []int{pre, cur - 1})
        }
        pre = cur + 1
    }
    if pre <= upper {
        ans = append(ans, []int{pre, upper})
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function findDisappearedNumbers(nums: number[], lower: number, upper: number): number[][] {
    nums.sort((a, b) => a - b);
    const l = _.sortedIndex(nums, lower);
    const r = _.sortedIndex(nums, upper + 1);
    const ans: number[][] = [];
    let pre = lower;

    for (let i = l; i < r; i++) {
        const cur = nums[i];
        if (pre < cur) {
            ans.push([pre, cur - 1]);
        }
        pre = cur + 1;
    }

    if (pre <= upper) {
        ans.push([pre, upper]);
    }
    return ans;
}

评论