给你n个整数nums,在其中任选3个下标i, j, k, 让它们构成一个三角形,时间复杂度不能大于等于O(n^3)
时间: 2024-06-06 21:07:55 浏览: 7
可以先将数组nums排序,然后枚举最长边的下标k,然后再枚举另外两条边的下标i和j,使得nums[i] + nums[j] > nums[k],即这三个数可以构成一个三角形。由于数组已经排序,所以只需要判断一次即可。
时间复杂度为O(n^2),因为排序的时间复杂度为O(nlogn),枚举i和j的时间复杂度为O(n^2)。
相关问题
给你n个整数nums,在其中任选3个下标i, j, k, 满足i < j < k, 让它们构成一个三角形,时间复杂度不能大于等于O(n^3)
可以先对数组进行排序,然后从小到大枚举三个数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)。
给你一个整数数组nums,请计算数组的中心下标
好的,计算数组的中心下标可以使用以下方法:
1. 先计算出数组的总和 sum,然后从左往右遍历数组,同时维护一个 left_sum 变量表示当前左边元素的总和。如果 left_sum 等于 sum 减去当前元素值和 left_sum 的差(即右边元素的总和),那么当前下标就是中心下标。
2. 如果左边元素总和与右边元素总和相等,那么当前下标就是中心下标。
下面是使用 Python 实现上述算法的代码:
``` python
def pivotIndex(nums):
sum = 0
for num in nums:
sum += num
left_sum = 0
for i in range(len(nums)):
if left_sum == sum - nums[i] - left_sum:
return i
left_sum += nums[i]
return -1
```
这个函数接受一个整数数组 nums 作为输入,并返回中心下标。如果不存在中心下标,则返回 -1。
相关推荐
![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)