给你n个整数nums,在其中任选3个下标i, j, k, 满足i < j < k, 让它们构成一个三角形,时间复杂度不能大于等于O(n^3)
时间: 2024-05-24 21:11:19 浏览: 6
可以先对数组进行排序,然后从小到大枚举三个数a[i]、a[j]、a[k],其中i<j<k。如果a[i]+a[j]>a[k],那么这三个数可以构成一个三角形,因为任意两边之和大于第三边。同时,由于数组已经排好序,所以如果a[i]+a[j]<=a[k],那么对于任意i'<=i和j'>=j,都有a[i']+a[j']<=a[k],因此就不需要再枚举i和j了,直接枚举下一个k即可。这样时间复杂度就是O(n^2)。
相关问题
给你n个整数nums,在其中任选3个下标i, j, k, 让它们构成一个三角形,时间复杂度不能大于等于O(n^3)
可以先将数组nums排序,然后枚举最长边的下标k,然后再枚举另外两条边的下标i和j,使得nums[i] + nums[j] > nums[k],即这三个数可以构成一个三角形。由于数组已经排序,所以只需要判断一次即可。
时间复杂度为O(n^2),因为排序的时间复杂度为O(nlogn),枚举i和j的时间复杂度为O(n^2)。
给你一个下标从 0 开始的整数数组 nums 和两个整数 key 和 k 。K 近邻下标 是 nums 中的一个下标 i ,并满足至少存在一个下标 j 使得 |i - j| <= k 且 nums[j] == key 。 以列表形式返回按 递增顺序 排序的所有 K 近邻下标。
好的,这是一个算法问题。我可以为您解释一下如何解决这个问题。
首先,我们可以遍历整个数组,对于每个元素,检查它是否等于 key。如果等于,我们再检查它与之前的 k 个元素是否距离小于等于 k,以及它与之后的 k 个元素是否距离小于等于 k。如果满足条件,我们就把它的下标加入到结果集合中。
具体来说,我们可以使用一个双端队列来维护当前元素之前的 k 个元素,以及一个指针来指向当前元素之前的 k 个元素的队首。对于每个元素,我们先检查它与队首的距离是否大于 k,如果大于,就把队首出队。然后再检查它与队尾的距离是否小于等于 k,如果小于等于,就把队尾入队。最终队列中剩下的元素就是与当前元素距离小于等于 k 的元素,它们的下标就是当前元素的 k 近邻下标。
最后,我们把所有满足要求的下标按照递增顺序排序,即可得到最终的结果。
以下是 Python 代码实现:
```python
from collections import deque
def find_k_neighbors(nums, key, k):
n = len(nums)
queue = deque()
res = []
for i in range(n):
if nums[i] == key:
while queue and i - queue[0] > k:
queue.popleft()
while queue and nums[i] - nums[queue[-1]] > k:
queue.pop()
queue.append(i)
if queue and i - queue[0] <= k:
res.append(queue[0])
return sorted(res)
```
希望能够解决您的问题。
相关推荐
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)