i******r
发帖数: 793 | 1 给一个int数组，要求在里面找到一个未排序的子数组。
如果把该子数组排序，那么原数组就是有序的。
例子：
2 (6 4 8 10 9) 15
把括号里面的subarray排序后，整个数组就是有序的
我当时想了一个O(N)的算法，后来发现在某些条件下算法是错的 |
n*******s
发帖数: 17267 | |
n*******s
发帖数: 17267 | 3 不对。。。
【在 n*******s 的大作中提到】
: 不就是两头找最大排序序列然后。。。
|
i******r
发帖数: 793 | 4 我当时也是这样想的，但是下面这种情况怎么办：
1 8 9 2 4 5
两头升序中间没有元素
【在 n*******s 的大作中提到】
: 不就是两头找最大排序序列然后。。。
|
n*******s
发帖数: 17267 | 5 还可以有其它情况，直觉是这种直接重新排得了，现在的机器这么多，这么快，但不能
这么回答。
感觉是这种除非中间的数组排好序后刚好能与两头交接上，否则真不够折腾的。
【在 i******r 的大作中提到】
: 我当时也是这样想的，但是下面这种情况怎么办：
: 1 8 9 2 4 5
: 两头升序中间没有元素
|
n*****x
发帖数: 686 | 6 维护一个stack，里面存index。还要记录当前见过的最大值。开始扫数组
比当前最大大就push，比top指的数字小就pop，不然就continue。扫一边数组。
然后开始pop stack，index间隔不是1的就是你要找到的，最后一个元素和-1比。top需
要是n-1。应该算On
vector solve(vector& nums){
vector res(2,-1);
int n = nums.size();
if (n==0) return res;
stack stk;
stk.push(-1);
int max_sofar = nums[0];
for (int i=0; i
while (stk.size()!=1 && nums[stk.top()]>nums[i]) stk.pop();
if (nums[i]>=max_sofar){
max_sofar = nums[i];
stk.push(i);
}
}
int right=n;
while (!stk.empty()){
int left = stk.top();
stk.pop();
if (right-left>1) return vector({left+1,right-1});
right = left;
}
return res;
}
【在 i******r 的大作中提到】
: 给一个int数组，要求在里面找到一个未排序的子数组。
: 如果把该子数组排序，那么原数组就是有序的。
: 例子：
: 2 (6 4 8 10 9) 15
: 把括号里面的subarray排序后，整个数组就是有序的
: 我当时想了一个O(N)的算法，后来发现在某些条件下算法是错的
|
D**F
发帖数: 76 | 7 可不可以这样想，指针在两头分别找到各自的最长升序序列[0..left]、[right,n - 1]
，这样的话数组分为了左中右三个部分。
在左部分中查找刚好比[中部分+右部分]的min value大或相等的元素位置作为答案的左
边界，在右部分中查找刚好比[左部分+中部分]的max value小或相等的元素位置作为答
案的右边界。 |
s*****p
发帖数: 30 | 8 咱两想法一样
1]
【在 D**F 的大作中提到】
: 可不可以这样想，指针在两头分别找到各自的最长升序序列[0..left]、[right,n - 1]
: ，这样的话数组分为了左中右三个部分。
: 在左部分中查找刚好比[中部分+右部分]的min value大或相等的元素位置作为答案的左
: 边界，在右部分中查找刚好比[左部分+中部分]的max value小或相等的元素位置作为答
: 案的右边界。
|
n*******s
发帖数: 17267 | 9 如果一定存在的话，倒是可以做，就用楼上最后两行的思路 |
n*******s
发帖数: 17267 | |
|
|
D**F
发帖数: 76 | 11 根据楼上的思想写了两个版本,不知道对不对
单调栈:
List findMinUnsortedSubArray(int[] nums) {
List res = new ArrayList<>(2);
if (nums == null || nums.length == 0) return res;
int n = nums.length;
Stack s = new Stack<>();
int max = Integer.MIN_VALUE;
s.push(-1);
for (int i=0; i
while (!s.isEmpty() && nums[i] < max && nums[i] < nums[s.peek()]
) {
s.pop();
}
if (nums[i] >= max) {
max = nums[i];
s.push(i);
}
}
int lastInd = n;
int left = n, right = 0;
while (!s.isEmpty()) {
int curInd = s.pop();
if (lastInd - curInd > 1) {
right = Math.max(right, lastInd);
left = Math.min(left, curInd);
}
lastInd = curInd;
}
res.add(left + 1);
res.add(right - 1);
return res;
}
数组处理:
List findMinUnsortedSubArrayII(int[] nums) {
List res = new ArrayList<>(2);
if (nums == null || nums.length == 0) return res;
int n = nums.length;
int left = 0, right = n - 1;
while (left < n - 1 && nums[left] <= nums[left + 1]) ++left;
if (left == n - 1) return res;
while (right > 0 && nums[right] >= nums[right - 1]) --right;
int rightMin = Integer.MAX_VALUE, leftMax = Integer.MIN_VALUE;
// may be replaced by binary search
for (int i=left+1; i
rightMin = Math.min(rightMin, nums[i]);
}
for (int i=0; i
leftMax = Math.max(leftMax, nums[i]);
}
int leftSub = 0, rightSub = n - 1;
while (leftSub <= left && nums[leftSub] <= rightMin) ++leftSub;
while (rightSub >= right && nums[rightSub] >= leftMax) -- rightSub;
if (leftSub >= rightSub) return res;
res.add(leftSub);
res.add(rightSub);
return res;
} |
n*****x
发帖数: 686 | 12 第一个有bug，你push了-1，不能check empty。
我写了一个贴在我的回复里了。
【在 D**F 的大作中提到】
: 根据楼上的思想写了两个版本,不知道对不对
: 单调栈:
: List findMinUnsortedSubArray(int[] nums) {
: List res = new ArrayList<>(2);
: if (nums == null || nums.length == 0) return res;
: int n = nums.length;
: Stack s = new Stack<>();
: int max = Integer.MIN_VALUE;
: s.push(-1);
: for (int i=0; i
|
D**F
发帖数: 76 | 13 我有处理呀，!s.isEmpty() && nums[i] < max 这个可以搞定-1的情况
【在 n*****x 的大作中提到】
: 第一个有bug，你push了-1，不能check empty。
: 我写了一个贴在我的回复里了。
|
H********k
发帖数: 122 | 14 放到2叉树里，用in-order找最大的不是bst的子树。 |
b******7
发帖数: 8200 | 15 这是不是longest palindrome substring 的变形啊。
就是选一个数，两边的要么都比他小，要么都比他大？
【在 i******r 的大作中提到】
: 给一个int数组，要求在里面找到一个未排序的子数组。
: 如果把该子数组排序，那么原数组就是有序的。
: 例子：
: 2 (6 4 8 10 9) 15
: 把括号里面的subarray排序后，整个数组就是有序的
: 我当时想了一个O(N)的算法，后来发现在某些条件下算法是错的
|
n*****x
发帖数: 686 | 16 想出来一个更简单的one pass，从两边找到连续升序，降序，然后扫中间，调整左右
pointers。
vector Solution::subUnsort(vector &nums) {
vector res(2,-1);
int n = nums.size();
if (n==0) return res;
int i=0, j=n-1;
while (i=nums[i]) i++;
if (i==n-1) return res;
while (j>0 && nums[j-1]<=nums[j]) j--;
int end=j;
for (int k=i; k<=end; k++){
while (i>=0 && nums[i]>nums[k]) i--;
while (j<=n-1 && nums[j]
}
return vector({i+1,j-1});
} |
C*******A
发帖数: 1980 | 17 static int[] findSub(int[] arr)
{
int[] result =new int[2];
int s=-1, e=-1,min=Int32.MaxValue,max=Int32.MinValue;
for (int i = 0; i < arr.Length-1; i++)
{
if (arr[i] > arr[i + 1])
{
s = i + 1;
break;
}
}
for (int i = arr.Length - 1;i>0; i--)
{
if (arr[i - 1] > arr[i])
{
e = i - 1;
break;
}
}
for (int i = s; i <=e; i++)
{
min = min < arr[i] ? min : arr[i];
max = max > arr[i] ? max : arr[i];
}
for(int i=0;i
{
if (arr[i] > min)
{
result[0] = i;
break;
}
};
for (int i = arr.Length - 1; i > 0; i--)
{
if (arr[i] < max)
{
result[1] = i;
break;
}
}
return result;
} |
L***s
发帖数: 1148 | |
