Skip to content

Commit ec2c823

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.1966
No.1966.Binary Searchable Numbers in an Unsorted Array
1 parent eafd281 commit ec2c823

File tree

6 files changed

+293
-2
lines changed

6 files changed

+293
-2
lines changed

‎solution/1900-1999/1966.Binary Searchable Numbers in an Unsorted Array/README.md

Lines changed: 112 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -74,22 +74,133 @@ func(sequence, target)
7474

7575
<!-- 这里可写通用的实现逻辑 -->
7676

77+
**方法一：维护前缀最大值和后缀最小值**
78+
79+
我们注意到，对于数组中的每个元素，如果它是可被二分搜索的，那么需要满足两个条件：
80+
81+
1. 这个元素大于它的左边所有元素，否则，如果左边存在比当前元素大的元素，那么就会被移除，导致无法找到当前元素；
82+
2. 这个元素小于它的右边所有元素，否则，如果右边存在比当前元素小的元素，那么就会被移除，导致无法找到当前元素。
83+
84+
我们创建一个数组 $ok$，其中 $ok[i]$ 表示 $nums[i]$ 是否是可被二分搜索的。初始时，$ok[i]$ 都为 $1$。
85+
86+
我们先从左到右遍历数组，维护前缀最大值 $mx$，如果当前元素 $x$ 比 $mx$ 小，那么 $x$ 就不是可被二分搜索的，我们将 $ok[i]$ 置为 $0$，否则，我们将 $mx$ 更新为 $x$。
87+
88+
然后我们从右到左遍历数组，维护后缀最小值 $mi$，如果当前元素 $x$ 比 $mi$ 大，那么 $x$ 就不是可被二分搜索的，我们将 $ok[i]$ 置为 $0$，否则，我们将 $mi$ 更新为 $x$。
89+
90+
最后我们统计 $ok$ 中的 $1$ 的个数，即为可被二分搜索的元素的个数。
91+
92+
时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $nums$ 的长度。
93+
7794
<!-- tabs:start -->
7895

7996
### **Python3**
8097

8198
<!-- 这里可写当前语言的特殊实现逻辑 -->
8299

83100
```python
84-
101+
class Solution:
102+
def binarySearchableNumbers(self, nums: List[int]) -> int:
103+
n = len(nums)
104+
ok = [1] * n
105+
mx, mi = -1000000, 1000000
106+
for i, x in enumerate(nums):
107+
if x < mx:
108+
ok[i] = 0
109+
else:
110+
mx = x
111+
for i in range(n - 1, -1, -1):
112+
if nums[i] > mi:
113+
ok[i] = 0
114+
else:
115+
mi = nums[i]
116+
return sum(ok)
85117
```
86118

87119
### **Java**
88120

89121
<!-- 这里可写当前语言的特殊实现逻辑 -->
90122

91123
```java
124+
class Solution {
125+
public int binarySearchableNumbers(int[] nums) {
126+
int n = nums.length;
127+
int[] ok = new int[n];
128+
Arrays.fill(ok, 1);
129+
int mx = -1000000, mi = 1000000;
130+
for (int i = 0; i < n; ++i) {
131+
if (nums[i] < mx) {
132+
ok[i] = 0;
133+
}
134+
mx = Math.max(mx, nums[i]);
135+
}
136+
int ans = 0;
137+
for (int i = n - 1; i >= 0; --i) {
138+
if (nums[i] > mi) {
139+
ok[i] = 0;
140+
}
141+
mi = Math.min(mi, nums[i]);
142+
ans += ok[i];
143+
}
144+
return ans;
145+
}
146+
}
147+
```
148+
149+
### **C++**
150+
151+
```cpp
152+
class Solution {
153+
public:
154+
int binarySearchableNumbers(vector<int>& nums) {
155+
int n = nums.size();
156+
vector<int> ok(n, 1);
157+
int mx = -1000000, mi = 1000000;
158+
for (int i = 0; i < n; ++i) {
159+
if (nums[i] < mx) {
160+
ok[i] = 0;
161+
}
162+
mx = max(mx, nums[i]);
163+
}
164+
int ans = 0;
165+
for (int i = n - 1; i >= 0; --i) {
166+
if (nums[i] > mi) {
167+
ok[i] = 0;
168+
}
169+
mi = min(mi, nums[i]);
170+
ans += ok[i];
171+
}
172+
return ans;
173+
}
174+
};
175+
```
92176
177+
### **Go**
178+
179+
```go
180+
func binarySearchableNumbers(nums []int) (ans int) {
181+
n := len(nums)
182+
ok := make([]int, n)
183+
for i := range ok {
184+
ok[i] = 1
185+
}
186+
mx, mi := -1000000, 1000000
187+
for i, x := range nums {
188+
if x < mx {
189+
ok[i] = 0
190+
} else {
191+
mx = x
192+
}
193+
}
194+
for i := n - 1; i >= 0; i-- {
195+
if nums[i] > mi {
196+
ok[i] = 0
197+
} else {
198+
mi = nums[i]
199+
}
200+
ans += ok[i]
201+
}
202+
return
203+
}
93204
```
94205

95206
### **...**

‎solution/1900-1999/1966.Binary Searchable Numbers in an Unsorted Array/README_EN.md

Lines changed: 95 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -73,13 +73,107 @@ Because only -1 is guaranteed to be found, you should return 1.
7373
### **Python3**
7474

7575
```python
76-
76+
class Solution:
77+
def binarySearchableNumbers(self, nums: List[int]) -> int:
78+
n = len(nums)
79+
ok = [1] * n
80+
mx, mi = -1000000, 1000000
81+
for i, x in enumerate(nums):
82+
if x < mx:
83+
ok[i] = 0
84+
else:
85+
mx = x
86+
for i in range(n - 1, -1, -1):
87+
if nums[i] > mi:
88+
ok[i] = 0
89+
else:
90+
mi = nums[i]
91+
return sum(ok)
7792
```
7893

7994
### **Java**
8095

8196
```java
97+
class Solution {
98+
public int binarySearchableNumbers(int[] nums) {
99+
int n = nums.length;
100+
int[] ok = new int[n];
101+
Arrays.fill(ok, 1);
102+
int mx = -1000000, mi = 1000000;
103+
for (int i = 0; i < n; ++i) {
104+
if (nums[i] < mx) {
105+
ok[i] = 0;
106+
}
107+
mx = Math.max(mx, nums[i]);
108+
}
109+
int ans = 0;
110+
for (int i = n - 1; i >= 0; --i) {
111+
if (nums[i] > mi) {
112+
ok[i] = 0;
113+
}
114+
mi = Math.min(mi, nums[i]);
115+
ans += ok[i];
116+
}
117+
return ans;
118+
}
119+
}
120+
```
121+
122+
### **C++**
123+
124+
```cpp
125+
class Solution {
126+
public:
127+
int binarySearchableNumbers(vector<int>& nums) {
128+
int n = nums.size();
129+
vector<int> ok(n, 1);
130+
int mx = -1000000, mi = 1000000;
131+
for (int i = 0; i < n; ++i) {
132+
if (nums[i] < mx) {
133+
ok[i] = 0;
134+
}
135+
mx = max(mx, nums[i]);
136+
}
137+
int ans = 0;
138+
for (int i = n - 1; i >= 0; --i) {
139+
if (nums[i] > mi) {
140+
ok[i] = 0;
141+
}
142+
mi = min(mi, nums[i]);
143+
ans += ok[i];
144+
}
145+
return ans;
146+
}
147+
};
148+
```
82149
150+
### **Go**
151+
152+
```go
153+
func binarySearchableNumbers(nums []int) (ans int) {
154+
n := len(nums)
155+
ok := make([]int, n)
156+
for i := range ok {
157+
ok[i] = 1
158+
}
159+
mx, mi := -1000000, 1000000
160+
for i, x := range nums {
161+
if x < mx {
162+
ok[i] = 0
163+
} else {
164+
mx = x
165+
}
166+
}
167+
for i := n - 1; i >= 0; i-- {
168+
if nums[i] > mi {
169+
ok[i] = 0
170+
} else {
171+
mi = nums[i]
172+
}
173+
ans += ok[i]
174+
}
175+
return
176+
}
83177
```
84178

85179
### **...**

‎solution/1900-1999/1966.Binary Searchable Numbers in an Unsorted Array/Solution.cpp

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
class Solution {
2+
public:
3+
int binarySearchableNumbers(vector<int>& nums) {
4+
int n = nums.size();
5+
vector<int> ok(n, 1);
6+
int mx = -1000000, mi = 1000000;
7+
for (int i = 0; i < n; ++i) {
8+
if (nums[i] < mx) {
9+
ok[i] = 0;
10+
}
11+
mx = max(mx, nums[i]);
12+
}
13+
int ans = 0;
14+
for (int i = n - 1; i >= 0; --i) {
15+
if (nums[i] > mi) {
16+
ok[i] = 0;
17+
}
18+
mi = min(mi, nums[i]);
19+
ans += ok[i];
20+
}
21+
return ans;
22+
}
23+
};

‎solution/1900-1999/1966.Binary Searchable Numbers in an Unsorted Array/Solution.go

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
func binarySearchableNumbers(nums []int) (ans int) {
2+
n := len(nums)
3+
ok := make([]int, n)
4+
for i := range ok {
5+
ok[i] = 1
6+
}
7+
mx, mi := -1000000, 1000000
8+
for i, x := range nums {
9+
if x < mx {
10+
ok[i] = 0
11+
} else {
12+
mx = x
13+
}
14+
}
15+
for i := n - 1; i >= 0; i-- {
16+
if nums[i] > mi {
17+
ok[i] = 0
18+
} else {
19+
mi = nums[i]
20+
}
21+
ans += ok[i]
22+
}
23+
return
24+
}

‎solution/1900-1999/1966.Binary Searchable Numbers in an Unsorted Array/Solution.java

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
class Solution {
2+
public int binarySearchableNumbers(int[] nums) {
3+
int n = nums.length;
4+
int[] ok = new int[n];
5+
Arrays.fill(ok, 1);
6+
int mx = -1000000, mi = 1000000;
7+
for (int i = 0; i < n; ++i) {
8+
if (nums[i] < mx) {
9+
ok[i] = 0;
10+
}
11+
mx = Math.max(mx, nums[i]);
12+
}
13+
int ans = 0;
14+
for (int i = n - 1; i >= 0; --i) {
15+
if (nums[i] > mi) {
16+
ok[i] = 0;
17+
}
18+
mi = Math.min(mi, nums[i]);
19+
ans += ok[i];
20+
}
21+
return ans;
22+
}
23+
}

‎solution/1900-1999/1966.Binary Searchable Numbers in an Unsorted Array/Solution.py

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

0 commit comments

Comments
 (0)