今天是一道簡(jiǎn)單的算法題, 然而我卻被LeetCode新提交的測(cè)試用例卡住了!
給定一個(gè)整數(shù)數(shù)組，判斷是否存在重復(fù)元素碰镜。
如果任何值在數(shù)組中出現(xiàn)至少兩次兢卵，函數(shù)返回 true。如果數(shù)組中每個(gè)元素都不相同绪颖，則返回 false秽荤。
示例 1:
輸入: [1,2,3,1]
輸出: true
示例 2:
輸入: [1,2,3,4]
輸出: false
示例 3:
輸入: [1,1,1,3,3,4,3,2,4,2]
輸出: true
暴力解法
bool containsDuplicate(int* nums, int numsSize) {
for(int i=0; i<numsSize; i++){
for(int j=i+1; j<numsSize; j++){
if(nums[i] == nums[j])
return true;
}
}
return false;
}
不出意外的, 這種時(shí)間復(fù)雜度達(dá)到O(n^2)的方法用 Python 實(shí)現(xiàn)超時(shí)
class Solution(object):
def containsDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
for i in range(len(nums)-1):
for j in range(i+1, len(nums)):
if(nums[i] == nums[j]):
return True
return False
空間換時(shí)間思想
如果這道題限定了數(shù)字的范圍小于等于數(shù)組大小,那么這種方法可以獲得接近O(n)的時(shí)間復(fù)雜度.
判斷的方法是構(gòu)建一個(gè)與數(shù)組temp[numsSize], 若temp[nums[i]]==0,則此位置為空, 改為1, 若非零則重復(fù).
但是題目中沒有限定, 這意味著負(fù)數(shù)、大于數(shù)組大小的數(shù)都可以使用,下面是錯(cuò)誤示范, 想看正確答案, 跳過這部分.
我想到了用類似散列線性探測(cè)法的方法, 用temp[nums[i]%numsSize]是否為0判斷有無重復(fù), 為0則賦值為nums[i]/numsSize但是小于數(shù)組的的數(shù)商為0,于是我在后面+1
但是這樣還是不能覆蓋所有樣例, 因?yàn)檫€有負(fù)數(shù)的情況, 于是我有用了一個(gè)flag變量與結(jié)果相乘, 再進(jìn)行判斷.
然而還是無法覆蓋...這次已經(jīng)到達(dá)第17個(gè)樣例, 什么問題呢?就是當(dāng)你的商為-1的時(shí)候, +1會(huì)變成0,這樣又沖突了....
如果你有興趣, 可以試試改這段代碼, 讓它通過測(cè)試, 估計(jì)速度不會(huì)特別差.
bool containsDuplicate(int* nums, int numsSize) {
int *temp;
int flag = 1;
// 申請(qǐng)標(biāo)記數(shù)組,對(duì)應(yīng)位置為除數(shù)值則表示已有
temp = (int *)malloc(sizeof(int)*(numsSize));
for(int i=0; i<numsSize; i++){
if(nums[i]<0)
{
nums[i]= -nums[i];
flag = -1;
}
if(temp[nums[i]%numsSize]==0){
// +1讓小于numsSize的數(shù)對(duì)應(yīng)位置的值大于0
temp[nums[i]%numsSize] = flag*(nums[i]/numsSize+1);
}
else if(temp[nums[i]%numsSize]!=0 &&
temp[nums[i]%numsSize] == (nums[i]/numsSize+1))
{
return true;
}
else{
}
}
return false;
}
正解
哈希是最快的算法, 其次是用快速排序, 結(jié)合遍歷.
Python在這里顯示出極強(qiáng)的簡(jiǎn)潔性, 用集合自帶的哈希算法, 只需一條語句就可以實(shí)現(xiàn)
def containsDuplicate(self, nums):
return len(set(nums))!=len(nums)
下面這個(gè)解法是網(wǎng)友給出的, 結(jié)構(gòu)是雙層嵌套, 但是運(yùn)行結(jié)果居然才8ms, 很神奇. 不知道是不是測(cè)試?yán)硬粔驑O端.
bool containsDuplicate(int* nums, int numsSize) {
for(int i=0; i<numsSize; i++){
for(int j = i-1; j>=0; j--){
if(nums[i] > nums[j])
break;
else if(nums[i] == nums[j])
return true;
}
}
return false;
}
