class Solution {
public:
int binarySearchableNumbers(vector<int>& nums) {
}
};
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] <= 105nums 中所有值都 不同.
提升: 如果 nums 存在 重复的值, 你会如何修改你的算法吗?
原站题解
golang 解法, 执行用时: 52 ms, 内存消耗: 8.9 MB, 提交时间: 2023-10-21 23:31:03
func binarySearchableNumbers(nums []int) int {
if len(nums)==0{
return 0
}
max := make([]int, len(nums)+1)
max[0] =-1000000
for i := 0; i < len(nums); i++ {
if max[i] < nums[i]{
max[i+1] = nums[i]
}else {
max[i+1] = max[i]
}
}
ans:=0
right := 1000000
for i := len(nums)-1; i >=0; i-- {
if nums[i]< right && nums[i]> max[i]{
ans++
}
if right > nums[i]{
right = nums[i]
}
}
return ans
}
java 解法, 执行用时: 3 ms, 内存消耗: 54.4 MB, 提交时间: 2023-10-21 23:30:51
class Solution {
public int binarySearchableNumbers(int[] nums) {
int n = nums.length;
int[] postMin = new int[n];
postMin[n - 1] = 100001;
for (int i = n - 2; i >= 0; i--) {
postMin[i] = Math.min(nums[i + 1], postMin[i + 1]);
}
int max = -100001;
int ans = 0;
for (int i = 0; i < n; i++) {
if (nums[i] > max && nums[i] < postMin[i]) ans++;
max = Math.max(max, nums[i]);
}
return ans;
}
}
python3 解法, 执行用时: 128 ms, 内存消耗: 26.8 MB, 提交时间: 2023-10-21 23:30:21
from typing import List
class Solution:
def binarySearchableNumbers(self, nums: List[int]) -> int:
max_val = -0x7ffffffff
n = len(nums)
flag = [1] * n
for i in range(n):
if max_val > nums[i]:
flag[i] = 0
max_val = max(max_val, nums[i])
min_val = 0x7ffffffff
for i in range(n-1, -1, -1):
if min_val < nums[i]:
flag[i] = 0
min_val = min(min_val, nums[i])
return sum(flag)
def binarySearchableNumbers2(self, nums: List[int]) -> int:
n = len(nums)
l, r = float('-inf'), float('inf')
has = [0] * n
for i in range(n):
j = n-1-i
vi, vj = nums[i], nums[j]
if vi > l:
l = vi
has[i] += 1
if vj < r:
r = vj
has[j] += 1
return sum(i==2 for i in has)
cpp 解法, 执行用时: 64 ms, 内存消耗: 45.2 MB, 提交时间: 2023-10-21 23:29:46
const int N = 1e5 + 7;
class Solution {
public:
bool f[N];// 是否满足两个条件
int st[N];// 单调栈
int top;
int binarySearchableNumbers(vector<int>& nums) {
int res = 0;
int n = nums.size();
memset(f,true,n);
int mm = -1e9;
top = 0;
for(int i = 0;i < n;i ++) {
while(top && nums[i] < nums[st[top - 1]]) top --;
if(mm > nums[i]) f[i] = false;
st[top ++] = i;
mm = max(mm,nums[i]);
}
for(int i = 0;i < top;i ++) {
if(f[st[i]]) res ++;
}
return res;
}
};