Skip to content

Commit 323500a

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.1150. Check If a Number Is Majority Element in a Sorted Array
1 parent 5e9d13f commit 323500a

File tree

4 files changed

+200
-6
lines changed

4 files changed

+200
-6
lines changed

‎solution/1100-1199/1150.Check If a Number Is Majority Element in a Sorted Array/README.md

Lines changed: 68 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -42,27 +42,92 @@
4242
<li><code>1 <= target <= 10^9</code></li>
4343
</ul>
4444

45-
4645
## 解法
4746

4847
<!-- 这里可写通用的实现逻辑 -->
4948

49+
“二分查找”求 `target` 在数组 `nums` 中的左右边界。
50+
5051
<!-- tabs:start -->
5152

5253
### **Python3**
5354

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

5657
```python
57-
58+
class Solution:
59+
def isMajorityElement(self, nums: List[int], target: int) -> bool:
60+
def bsearch_left(nums, target, left, right):
61+
while left < right:
62+
mid = (left + right) >> 1
63+
if nums[mid] >= target:
64+
right = mid
65+
else:
66+
left = mid + 1
67+
return left if nums[left] == target else -1
68+
69+
def bsearch_right(nums, target, left, right):
70+
while left < right:
71+
mid = (left + right + 1) >> 1
72+
if nums[mid] <= target:
73+
left = mid
74+
else:
75+
right = mid - 1
76+
return left if nums[left] == target else -1
77+
78+
n = len(nums)
79+
left = bsearch_left(nums, target, 0, n - 1)
80+
if left == -1:
81+
return False
82+
right = bsearch_right(nums, target, left, n - 1)
83+
if right == -1:
84+
return False
85+
return right - left + 1 > n >> 1
5886
```
5987

6088
### **Java**
6189

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

6492
```java
65-
93+
class Solution {
94+
public boolean isMajorityElement(int[] nums, int target) {
95+
int n = nums.length;
96+
int left = bsearchLeft(nums, target, 0, n - 1);
97+
if (left == -1) {
98+
return false;
99+
}
100+
int right = bsearchRight(nums, target, left, n - 1);
101+
if (right == -1) {
102+
return false;
103+
}
104+
return right - left + 1 > (n >> 1);
105+
}
106+
107+
private int bsearchLeft(int[] nums, int target, int left, int right) {
108+
while (left < right) {
109+
int mid = (left + right) >> 1;
110+
if (nums[mid] >= target) {
111+
right = mid;
112+
} else {
113+
left = mid + 1;
114+
}
115+
}
116+
return nums[left] == target ? left : -1;
117+
}
118+
119+
private int bsearchRight(int[] nums, int target, int left, int right) {
120+
while (left < right) {
121+
int mid = (left + right + 1) >> 1;
122+
if (nums[mid] <= target) {
123+
left = mid;
124+
} else {
125+
right = mid - 1;
126+
}
127+
}
128+
return nums[left] == target ? left : -1;
129+
}
130+
}
66131
```
67132

68133
### **...**

‎solution/1100-1199/1150.Check If a Number Is Majority Element in a Sorted Array/README_EN.md

Lines changed: 66 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -39,21 +39,84 @@ Thus, 101 is not a majority element because 2 &gt; 4/2 is false.
3939
<li><code>1 &lt;= target &lt;= 10^9</code></li>
4040
</ul>
4141

42-
4342
## Solutions
4443

4544
<!-- tabs:start -->
4645

4746
### **Python3**
4847

4948
```python
50-
49+
class Solution:
50+
def isMajorityElement(self, nums: List[int], target: int) -> bool:
51+
def bsearch_left(nums, target, left, right):
52+
while left < right:
53+
mid = (left + right) >> 1
54+
if nums[mid] >= target:
55+
right = mid
56+
else:
57+
left = mid + 1
58+
return left if nums[left] == target else -1
59+
60+
def bsearch_right(nums, target, left, right):
61+
while left < right:
62+
mid = (left + right + 1) >> 1
63+
if nums[mid] <= target:
64+
left = mid
65+
else:
66+
right = mid - 1
67+
return left if nums[left] == target else -1
68+
69+
n = len(nums)
70+
left = bsearch_left(nums, target, 0, n - 1)
71+
if left == -1:
72+
return False
73+
right = bsearch_right(nums, target, left, n - 1)
74+
if right == -1:
75+
return False
76+
return right - left + 1 > n >> 1
5177
```
5278

5379
### **Java**
5480

5581
```java
56-
82+
class Solution {
83+
public boolean isMajorityElement(int[] nums, int target) {
84+
int n = nums.length;
85+
int left = bsearchLeft(nums, target, 0, n - 1);
86+
if (left == -1) {
87+
return false;
88+
}
89+
int right = bsearchRight(nums, target, left, n - 1);
90+
if (right == -1) {
91+
return false;
92+
}
93+
return right - left + 1 > (n >> 1);
94+
}
95+
96+
private int bsearchLeft(int[] nums, int target, int left, int right) {
97+
while (left < right) {
98+
int mid = (left + right) >> 1;
99+
if (nums[mid] >= target) {
100+
right = mid;
101+
} else {
102+
left = mid + 1;
103+
}
104+
}
105+
return nums[left] == target ? left : -1;
106+
}
107+
108+
private int bsearchRight(int[] nums, int target, int left, int right) {
109+
while (left < right) {
110+
int mid = (left + right + 1) >> 1;
111+
if (nums[mid] <= target) {
112+
left = mid;
113+
} else {
114+
right = mid - 1;
115+
}
116+
}
117+
return nums[left] == target ? left : -1;
118+
}
119+
}
57120
```
58121

59122
### **...**

‎solution/1100-1199/1150.Check If a Number Is Majority Element in a Sorted Array/Solution.java

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
class Solution {
2+
public boolean isMajorityElement(int[] nums, int target) {
3+
int n = nums.length;
4+
int left = bsearchLeft(nums, target, 0, n - 1);
5+
if (left == -1) {
6+
return false;
7+
}
8+
int right = bsearchRight(nums, target, left, n - 1);
9+
if (right == -1) {
10+
return false;
11+
}
12+
return right - left + 1 > (n >> 1);
13+
}
14+
15+
private int bsearchLeft(int[] nums, int target, int left, int right) {
16+
while (left < right) {
17+
int mid = (left + right) >> 1;
18+
if (nums[mid] >= target) {
19+
right = mid;
20+
} else {
21+
left = mid + 1;
22+
}
23+
}
24+
return nums[left] == target ? left : -1;
25+
}
26+
27+
private int bsearchRight(int[] nums, int target, int left, int right) {
28+
while (left < right) {
29+
int mid = (left + right + 1) >> 1;
30+
if (nums[mid] <= target) {
31+
left = mid;
32+
} else {
33+
right = mid - 1;
34+
}
35+
}
36+
return nums[left] == target ? left : -1;
37+
}
38+
}

‎solution/1100-1199/1150.Check If a Number Is Majority Element in a Sorted Array/Solution.py

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
class Solution:
2+
def isMajorityElement(self, nums: List[int], target: int) -> bool:
3+
def bsearch_left(nums, target, left, right):
4+
while left < right:
5+
mid = (left + right) >> 1
6+
if nums[mid] >= target:
7+
right = mid
8+
else:
9+
left = mid + 1
10+
return left if nums[left] == target else -1
11+
12+
def bsearch_right(nums, target, left, right):
13+
while left < right:
14+
mid = (left + right + 1) >> 1
15+
if nums[mid] <= target:
16+
left = mid
17+
else:
18+
right = mid - 1
19+
return left if nums[left] == target else -1
20+
21+
n = len(nums)
22+
left = bsearch_left(nums, target, 0, n - 1)
23+
if left == -1:
24+
return False
25+
right = bsearch_right(nums, target, left, n - 1)
26+
if right == -1:
27+
return False
28+
return right - left + 1 > n >> 1

0 commit comments

Comments
 (0)