當前位置:網站首頁>【Leetcode】442. 數組中重複的數據

【Leetcode】442. 數組中重複的數據

2022-05-14 04:50:30promise_yaner

題目鏈接:數組中重複的數據

題目描述:

給你一個長度為 n 的整數數組 nums ,其中 nums 的所有整數都在範圍 [1, n] 內,且每個整數出現 一次 或 兩次 。請你找出所有出現 兩次 的整數,並以數組形式返回。

你必須設計並實現一個時間複雜度為 O(n) 且僅使用常量額外空間的算法解决此問題。

分析:

1)題目要求的時間複雜度為O(n),空間複雜度為O(1)。說明需要使用哈希錶,但不能借助另外的哈希錶。

2)又因為數組長度為n,索引是[0,n-1],數據範圍是[1,n],所以可以使用原地哈希的方式。即原地修改數組nums為哈希錶。

具體方法有:

方法一:將nums[i]%n作為新的索引j,j的範圍為[0,n-1],若nums[j]<n,說明nums[i]%n是第一次出現,將nums[j]+=n。那麼之後若nums[j]>n,說明nums[i]%n是第二次出現。

方法二:將|nums[i]|-1作為新的索引j,(|nums[i]|錶示取絕對值),j的範圍為[0,n-1],若nums[j]>0,說明|nums[i]|-1是第一次出現,將nums[j]取反。那麼之後若nums[j]<0,說明|nums[i]|-1就是第二次出現。

代碼如下:

var findDuplicates = function(nums) {
    const n=nums.length;
    let res=[]
    for(let i=0;i<n;i++){
        if(nums[nums[i]%n]>n)
            res.push(nums[i]%n==0?n:nums[i]%n);
        nums[nums[i]%n]+=n;
    }
    return res;
};
var findDuplicates = function(nums) {
    const n=nums.length;
    let res=[]
    for(let i=0;i<n;i++){
        let x=Math.abs(nums[i]);
        if(nums[x-1]<0)
            res.push(x);
        else
            nums[x-1]=-nums[x-1];
    }
    return res;
};

版權聲明
本文為[promise_yaner]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/134/202205140427492341.html

隨機推薦