[697] Degree of an Array

咦竟然是這題XD！

我還以為是sliding window！原來不是嗎XD（笑我自己廢）

比起昨天寫的，發現在找左右index的時候，其實左邊根本不用從頭開始找QQ

但再看了大神們的解法之後，發現還有更快的方法RRR

天啊我真的好沒有慧根喔QQ

可喜可賀的是一次PASS  XD 先貼個原版: 

int findShortestSubArray(int* nums, int numsSize) {

int *counts= calloc(50000, sizeof(int));

int degree= 0;

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

{

counts[nums[i]]++;

if (counts[nums[i]] > degree)

degree = counts[nums[i]];

}

int ret = numsSize;

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

{

if (degree == counts[nums[i]])

{

int r= numsSize-1;

while (nums[r]!= nums[i])

r--;

if (ret > (r-i+1))

ret = r-i+1;

counts[nums[i]]=0;

}

}

return ret;

}

然後是，說是要一個loop跑完！！！

當degree被更新時，更新degree和ret

當數字是等於最高degree的時候，需要更新它的ret

感覺很容易漏掉它的degree變化的時候要更新的這件事！！！

還有，當這個數字不是最高degree的時候，我們可以不要管它(吧)

#define min(A,B) (A<B)?(A):(B)

int findShortestSubArray(int* nums, int numsSize) {

int *counts= calloc(50000, sizeof(int));

int *index= calloc(50000, sizeof(int));

int degree= 0;

int ret = INT_MAX;

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

{

counts[nums[i]]++;

if (index[nums[i]]==0)

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

else if (counts[nums[i]] == degree)

ret = min(ret,i-index[nums[i]]+2);

if (counts[nums[i]] > degree)

{

degree = counts[nums[i]];

ret = i-index[nums[i]]+2;

}

}

return ret;

}