LeetCode581. 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 <=.
my program
思路:构建一个排序好的数组,然后与原数组进行对比,找出最先和最后不同的元素,相减+1即为所求答案。此算法时间复杂度是O(nlogn),空间复杂度是O(n).
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
vector<int> tmp = nums;
sort(tmp.begin(), tmp.end());
int i = 0;
int j = nums.size() -1;
for (; i< nums.size(); i++) {
if (nums[i] != tmp[i])
break;
}
if (i >= nums.size())
return 0;
for (; j > 0; j--) {
if (nums[j] != tmp[j])
break;
}
return j - i + 1;
}
};
Submission Details
307 / 307 test cases passed.
Status: Accepted
Runtime: 56 ms
解法二
/**
* /------------\
* nums: [2, 6, 4, 8, 10, 9, 15]
* minr: 2 4 4 8 9 9 15
* <--------------------
* maxl: 2 6 6 8 10 10 15
* -------------------->
*/
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
int n = nums.size();
vector<int> maxlhs(n); // max number from left to cur
vector<int> minrhs(n); // min number from right to cur
for (int i = n - 1, minr = INT_MAX; i >= 0; i--) minrhs[i] = minr = min(minr, nums[i]);
for (int i = 0, maxl = INT_MIN; i < n; i++) maxlhs[i] = maxl = max(maxl, nums[i]);
int i = 0, j = n - 1;
while (i < n && nums[i] <= minrhs[i]) i++;
while (j > i && nums[j] >= maxlhs[j]) j--;
return j + 1 - i;
}
};
此算法时间复杂度仅是O(n),空间复杂度是O(n). 优于第一种算法
最新文章
- nandflash的读写(2440)
- HTML5之文件API
- PHP部分资料
- curl post
- 装X之读书籍
- js方式找出数组中重复数最多的那个数,并返回该数以及重复次数
- <;转>;.php导出excel(多种方法)
- sdut 2847 Monitor (思维题)
- solr 3.5 配置及server设置
- eclipse安装ADT插件重启后不显示Android SDK Manager和Android Virtual Device Manager图标的一种解决办法
- 添加网站QQ客服链接
- 搬瓦工搭建SS的教程
- Python——SQL——将查询的数据列表化
- Django:同一个app支持多个数据库
- vi中的全局替换
- hiho1255 Mysterious Antiques in Sackler Museum
- 使用new data计算时间以及格式转换
- tidb在DDL语句方面的测试
- Jfrog Artifactory 创建docker 镜像仓库以及 push 镜像到 该仓库.
- mysql如何处理亿级数据,第一个阶段——优化SQL语句