给你一个整数数组 arr ,请你删除一个子数组(可以为空),使得 arr 中剩下的元素是 非递减 的。 一个子数组指的是原数组中连续的一个子序列。 请你返回满足题目要求的最短子数组的长度。 C 语言
时间: 2023-05-26 14:05:04 浏览: 48
示例 1:
输入:arr = [1,2,3,10,4,2,3,5]
输出:3
解释:我们需要删除的最短子数组是 [10,4,2],长度为 3。剩余元素形成非递减数组 [1,2,3,3,5] 。
示例 2:
输入:arr = [5,4,3,2,1]
输出:1
解释:我们需要删除的最短子数组是 [5],长度为 1。
提示:
1 <= arr.length <= 10^5
0 <= arr[i] <= 10^9
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/shortest-subarray-to-be-removed-to-make-array-sorted
以下是C语言的解法:
相关问题
给你一个整数数组 arr ,请你删除一个子数组(可以为空),使得 arr 中剩下的元素是 非递减 的。 一个子数组指的是原数组中连续的一个子序列。 请你返回满足题目要求的最短子数组的长度。代码
思路:双指针法
从左到右遍历数组,若出现 arr[i] > arr[i+1] ,则一定需要删除 arr[i],但 arr[i] 是否需要删除还需进一步判断:
- 若存在 arr[i-1] > arr[i+1],则 arr[i] 不能单独删除,将 i 指针右移即可;
- 否则 arr[i] 需要删除。
同样,从右到左遍历数组,若出现 arr[i] > arr[i+1] , 则一定需要删除 arr[i+1],同理还需进一步判断。
最终,剩下的数组就是非递减的,返回数组长度即可。
参考代码如下:
给定一个整数数组,要求输出其升序排序后形成的数组。
您好!针对您的问题,可以使用常见的排序算法如快速排序(Quicksort)、归并排序(Mergesort)或堆排序(Heapsort)等来实现。
以快速排序为例,其思路如下:
1. 选取数组中的一个元素作为基准值(pivot);
2. 将数组中小于基准值的元素放到左边,大于基准值的元素放到右边;
3. 对左右两个子数组分别重复步骤 1 和步骤 2,直到子数组中只剩下一个元素。
以下是 Python 代码实现:
```python
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
left = [x for x in arr[1:] if x < pivot]
right = [x for x in arr[1:] if x >= pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
```
其中,列表推导式 `[x for x in arr[1:] if x < pivot]` 可以筛选出小于基准值的元素,而 `[x for x in arr[1:] if x >= pivot]` 可以筛选出大于等于基准值的元素。
调用示例:
```python
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = quick_sort(arr)
print(sorted_arr) # 输出 [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
```
希望可以帮助您!如果您有任何问题或者需要进一步帮助,请随时告诉我。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![py](https://img-home.csdnimg.cn/images/20210720083646.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)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)