[581] Shortest Unsorted Continuous Subarray

什麼，不可以用sorting嗎？！ XD

可惜我可是沒什麼bug的寫出來了呢～（撥瀏海）

int comp(const void *a, const void *b)

{

return (*(int*)a - *(int*)b);

}

int findUnsortedSubarray(int* nums, int numsSize) {

int *sort = calloc(numsSize, sizeof(int));

memcpy ( sort, nums, sizeof(int)*numsSize);

qsort(sort,numsSize, sizeof(int), comp);

int l=0, r=numsSize-1;

while (l<=r && nums[l] == sort[l])

l++;

while (l<=r && nums[r] == sort[r])

r--;

return r-l+1;

}

說要弄一個往右的目前最大，跟往左的目前最小，結果也沒有比較快，原來不用存兩個array去左邊右邊跟原array 相比來找index嗎哈哈哈（乾笑）

int findUnsortedSubarray(int* nums, int numsSize) {

int *up = calloc(numsSize, sizeof(int));//max

int *down = calloc(numsSize, sizeof(int));//min

up[0] = nums[0];

down[numsSize-1] = nums[numsSize-1];

for (int i=0; i<numsSize-1; i++)

{

if (nums[i+1]>up[i])

up[i+1] = nums[i+1];

else

up[i+1] = up[i];

int j=numsSize-1-i;

if (nums[j-1]<down[j])

down[j-1] = nums[j-1];

else

down[j-1]= down[j];

}

/* nums : [2,6,4,8,10,9,15]

2 6 6 8 10 10 15 up /max

2 4 4 8 9 9 15 down /min

*/

int l=0, r=numsSize-1;

while (l<numsSize-1 && down[l]==nums[l])

l++;

while (r>0 && up[r]==nums[r])

r--;

if (l<r)

return r-l+1;

else

return 0;

}

結果的結果只要用max, min 跟各自的index去記錄就好了...

這樣只要跑一次nums 結果就出來了！！！天才果然跟我想的不一樣啊 QQ

那可以跟有錢人想的一樣就好嗎？（痛哭）

備註一下，它要找的其實是: 右邊數過來的第二最大，跟左邊數過去的第二最小，

為什麼不是第一最大跟第一最小呢？因為max 跟 min 本來就是會留在原地的，我們要的是從小排到大啊啊啊～

int findUnsortedSubarray(int* nums, int numsSize) {

int max= INT_MIN;

int min = INT_MAX;

int r= -1, l = -1;

for (int i=0; i<numsSize; i++)

{

if (nums[i]>=max)

max = nums[i];

else

r=i;

int j=numsSize-1-i;

if (nums[j]<=min)

min = nums[j];

else

l=j;

}

if (l<0 || r<0)

return 0;

return r-l+1;

}