跳转至

1966. 未排序数组中的可被二分查找的数 🔒

难度中等

题目描述

有一个 类似 二分查找 的方法。 这个方法有两个入参: sequence 是一个整数数组， target 是一个整数。 这个方法可以判断 target 是否存在 sequence中。

该方法的伪代码如下：

func(sequence, target)
  while sequence is not empty
    randomly choose an element from sequence as the pivot
    if pivot = target, return true
    else if pivot < target, remove pivot and all elements to its left from the sequence
    else, remove pivot and all elements to its right from the sequence
  end while
  return false

当 sequence 是排好序时, 这个方法对 所有 值都可正常判断。如果 sequence 不是排好序的, 该方法并不是对所有值都可正常判断, 但对一些 值仍可正常判断。

给定一个仅包含不同数字的数组 nums表示 sequence， nums是否排序未知，对于 所有可能的选择, 返回通过这个方法保证能找到的值的数量。

 

示例 1:

输入: nums = [7]
输出: 1
解释: 
7 保证能被找到.
因为数组中只有一个数字, 7 一定会被选中. 因为选中的值等于target, 这个方法会返回 true.

示例 2:

输入: nums = [-1,5,2]
输出: 1
解释: 
只有 -1 保证能被找到.
如果 -1 被选中, 这个方法就会返回 true.
如果 5 被选中, 5 和 2 会被移除。 在下一次循环时, 这个序列只有一个元素： -1 ，这个方法就会返回 true.
如果 2 被选中, 2 将会被移除。 在下次循环时, 这个序列里将会有 -1 和 5. 无论哪个数字被选中, 这个方法都会找到 -1 且返回 true.

5 不能保证被找到。
如果 2 被选中, -1, 5 和 2 将会被移除。 这个序列将会被清空且这个方法会返回 false。

2 不能保证被找到.
如果 5 被选中, 5 和 2 将会被移除。在下次循环时, 这个序列只会有一个元素： -1 且这个方法会返回 false。

因为只有-1 是保证能被找到的, 你应该返回 1.

 

提示:

  • 1 <= nums.length <= 105
  • -105 <= nums[i] <= 105
  • nums 中所有值都 不同.

 

提升: 如果 nums 存在 重复的值, 你会如何修改你的算法吗? 

解法

方法一：维护前缀最大值和后缀最小值

思考

二分每次丢弃中点一侧。一个值能被搜到，必须大于左侧所有值且小于右侧所有值，否则错误的一半可能被丢掉。

从左维护前缀最大，从右维护后缀最小，两遍标记不满足者，最后统计仍合法的个数。

我们注意到，对于数组中的每个元素，如果它是可被二分搜索的，那么需要满足两个条件：

  1. 这个元素大于它的左边所有元素，否则，如果左边存在比当前元素大的元素，那么就会被移除，导致无法找到当前元素；
  2. 这个元素小于它的右边所有元素，否则，如果右边存在比当前元素小的元素，那么就会被移除，导致无法找到当前元素。

我们创建一个数组 \(ok\)，其中 \(ok[i]\) 表示 \(nums[i]\) 是否是可被二分搜索的。初始时 \(ok[i]\) 都为 \(1\)。

我们先从左到右遍历数组，维护前缀最大值 \(mx\)，如果当前元素 \(x\) 比 \(mx\) 小，那么 \(x\) 就不是可被二分搜索的，我们将 \(ok[i]\) 置为 \(0\)，否则，我们将 \(mx\) 更新为 \(x\)。

然后我们从右到左遍历数组，维护后缀最小值 \(mi\)，如果当前元素 \(x\) 比 \(mi\) 大，那么 \(x\) 就不是可被二分搜索的，我们将 \(ok[i]\) 置为 \(0\)，否则，我们将 \(mi\) 更新为 \(x\)。

最后我们统计 \(ok\) 中的 \(1\) 的个数，即为可被二分搜索的元素的个数。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为数组 \(nums\) 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def binarySearchableNumbers(self, nums: List[int]) -> int:
        n = len(nums)
        ok = [1] * n
        mx, mi = -1000000, 1000000
        for i, x in enumerate(nums):
            if x < mx:
                ok[i] = 0
            else:
                mx = x
        for i in range(n - 1, -1, -1):
            if nums[i] > mi:
                ok[i] = 0
            else:
                mi = nums[i]
        return sum(ok)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int binarySearchableNumbers(int[] nums) {
        int n = nums.length;
        int[] ok = new int[n];
        Arrays.fill(ok, 1);
        int mx = -1000000, mi = 1000000;
        for (int i = 0; i < n; ++i) {
            if (nums[i] < mx) {
                ok[i] = 0;
            }
            mx = Math.max(mx, nums[i]);
        }
        int ans = 0;
        for (int i = n - 1; i >= 0; --i) {
            if (nums[i] > mi) {
                ok[i] = 0;
            }
            mi = Math.min(mi, nums[i]);
            ans += ok[i];
        }
        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
class Solution {
public:
    int binarySearchableNumbers(vector<int>& nums) {
        int n = nums.size();
        vector<int> ok(n, 1);
        int mx = -1000000, mi = 1000000;
        for (int i = 0; i < n; ++i) {
            if (nums[i] < mx) {
                ok[i] = 0;
            }
            mx = max(mx, nums[i]);
        }
        int ans = 0;
        for (int i = n - 1; i >= 0; --i) {
            if (nums[i] > mi) {
                ok[i] = 0;
            }
            mi = min(mi, nums[i]);
            ans += ok[i];
        }
        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
func binarySearchableNumbers(nums []int) (ans int) {
    n := len(nums)
    ok := make([]int, n)
    for i := range ok {
        ok[i] = 1
    }
    mx, mi := -1000000, 1000000
    for i, x := range nums {
        if x < mx {
            ok[i] = 0
        } else {
            mx = x
        }
    }
    for i := n - 1; i >= 0; i-- {
        if nums[i] > mi {
            ok[i] = 0
        } else {
            mi = nums[i]
        }
        ans += ok[i]
    }
    return
}

评论