【LeetCode】581. Shortest Unsorted Continuous Subarray 解题报告(Python & C++)
2024-09-05 07:18:33
作者: 负雪明烛
id: fuxuemingzhu
个人博客: http://fuxuemingzhu.cn/
题目地址:https://leetcode.com/problems/shortest-unsorted-continuous-subarray/description/
题目描述
Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.
You need to find the shortest such subarray and output its length.
Example 1:
Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
Note:
- Then length of the input array is in range [1, 10,000].
- The input array may contain duplicates, so ascending order here means <=.
解题方法
方法一:排序比较
这个题竟然真的是排序之后,然后和原来的数组进行比较得到的。
因为题目中的数组的长度最大只有1000,所以排序的时间不算很高。排序后的数组和之前的数组进行比较,找出最小的不相等的数字位置和最大不相等的数字的位置,两者的差相减+1即为所求。
class Solution(object):
def findUnsortedSubarray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
_len, _nums = len(nums), sorted(nums)
if nums == _nums:
return 0
l = min([i for i in range(_len) if nums[i] != _nums[i]])
r = max([i for i in range(_len) if nums[i] != _nums[i]])
return r - l + 1
二刷用到C++,代码如下:
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
const int N = nums.size();
auto t = nums;
sort(t.begin(), t.end());
int l = N, r = 0;
for (int i = 0; i < N; ++i) {
if (t[i] != nums[i]) {
l = min(l, i);
r = max(r, i);
}
}
return r >= l ? r - l + 1 : 0;
}
};
日期
2018 年 2 月 4 日
2018 年 11 月 27 日 —— 最近的雾霾太可怕
最新文章
- Java防止SQL注入(转)
- vs2015 生成项目时,提示执行失败,参数错误
- C++实现VPN工具之VPN错误代码大全
- Android 图标上面添加提醒使用开源UI类库 Viewbadger
- one-to-many many-to-one配置解释
- 【HDOJ】1421 搬寝室
- 【LeetCode练习题】Swap Nodes in Pairs
- java中的引用传递(同样适用于JS)
- laravel怎么创建一个简单的blog
- Jenkins时区设置为北京时间
- springdata jpa 原始sql的使用
- centos + nginx + php-fpm +mysql的简单配置
- PL/SQL学习笔记之记录
- 【题解】 [HAOI2016]食物链 (拓扑排序)
- MongoDB安装、CURD操作、使用场景分析总结(1)
- linux 查找
- java 实现 PDF 加水印功能
- 如何调用别人发布的WebService程序
- 无废话JavaScript(上)
- jquery滚动条插件nanoscroller的应用