当前位置:网站首页>LeetCode 1552. Magnetic force between two balls
LeetCode 1552. Magnetic force between two balls
2022-07-06 16:42:00 【Daylight629】
1552. The magnetic force between the two balls
Under the code name C-137 On the earth ,Rick Found that if he put two balls in his newly invented basket , There will be a special form of magnetic force between them .Rick Yes n
An empty basket , The first i
The position of the basket is position[i]
,Morty Want to put m
Put a ball in these baskets , Between any two balls Minimum magnetic force Maximum .
It is known that if two balls are located at x
and y
, Then the magnetic force between them is |x - y|
.
Give you an array of integers position
And an integer m
, Please return to maximize the minimum magnetic force .
Example 1:
Input :position = [1,2,3,4,7], m = 3
Output :3
explain : take 3 Put the balls in the 1,4 and 7 The three baskets , The magnetic force between the two balls is [3, 3, 6]. The minimum magnetic force is 3 . We can't make the minimum magnetic force greater than 3 .
Example 2:
Input :position = [5,4,3,2,1,1000000000], m = 2
Output :999999999
explain : We use the 1 and 1000000000 The basket has the minimum magnetic force and the maximum .
Tips :
n == position.length
2 <= n <= 10^5
1 <= position[i] <= 10^9
- all
position
The integer Different from each other . 2 <= m <= position.length
Two 、 Method 1
Two points search
class Solution {
public int maxDistance(int[] position, int m) {
Arrays.sort(position);
int l = 1;
int r = position[position.length - 1] - position[0];
int res = -1;
while (l <= r) {
int mid = l + ((r - l) >> 1);
if (check(mid, position, m)) {
res = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return res;
}
public boolean check(int x, int[] position, int m) {
int pre = position[0];
int cnt = 1;
for (int i = 1; i < position.length; i++) {
if (position[i] - pre >= x) {
pre = position[i];
cnt++;
}
}
return cnt >= m;
}
}
Complexity analysis
Time complexity :O(nlog(nS)), among n Is the number of baskets ,S Is the upper limit of basket position . Sorting basket positions requires O(nlogn) Time complexity of , Binary search divides the basket position interval , need O(logS) Time complexity of . Whether the statistical answer meets the requirements every time O(n) Time complexity of , So the total time complexity is O(nlogn+nlogS)=O(nlog(nS)).
Spatial complexity :O(logn), That is, the stack space required for sorting .
边栏推荐
- Chapter 5 namenode and secondarynamenode
- Bidirectional linked list - all operations
- Local visualization tools are connected to redis of Alibaba cloud CentOS server
- Investigation report of bench type Brinell hardness tester industry - market status analysis and development prospect prediction
- Codeforces Round #797 (Div. 3)无F
- Spark独立集群动态上线下线Worker节点
- Spark独立集群Worker和Executor的概念
- 原生js实现全选和反选的功能 --冯浩的博客
- Codeforces Global Round 19
- Market trend report, technological innovation and market forecast of China's double sided flexible printed circuit board (FPC)
猜你喜欢
随机推荐
Acwing: Game 58 of the week
Classic application of stack -- bracket matching problem
(lightoj - 1369) answering queries (thinking)
The concept of spark independent cluster worker and executor
业务系统从Oracle迁移到openGauss数据库的简单记录
Audio and video development interview questions
Sublime text code formatting operation
Problem - 1646C. Factorials and Powers of Two - Codeforces
Li Kou: the 81st biweekly match
Cmake Express
Hbuilder X格式化快捷键设置
Market trend report, technical innovation and market forecast of China's desktop capacitance meter
Effet d'utilisation, déclenché lorsque les composants de la fonction sont montés et déchargés
Codeforces Round #771 (Div. 2)
Chapter 1 overview of MapReduce
使用jq实现全选 反选 和全不选-冯浩的博客
Market trend report, technical innovation and market forecast of double-sided foam tape in China
Chapter 5 yarn resource scheduler
我在字节跳动「修电影」
Local visualization tools are connected to redis of Alibaba cloud CentOS server