建站
咨詢
售后
建站咨詢
新聞中心
本篇文章為大家展示了如何處理leetcode136只出現(xiàn)一次的數(shù)字，內(nèi)容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細(xì)介紹希望你能有所收獲。
涇源網(wǎng)站建設(shè)公司創(chuàng)新互聯(lián)建站,涇源網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為涇源數(shù)千家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\外貿(mào)網(wǎng)站制作要多少錢，請找那個(gè)售后服務(wù)好的涇源做網(wǎng)站的公司定做！
“好”算法的標(biāo)準(zhǔn)
對于一個(gè)問題的算法來說，之所以稱之為算法，首先它必須能夠解決這個(gè)問題（稱為準(zhǔn)確性）。其次，通過這個(gè)算法編寫的程序要求在任何情況下不能崩潰（稱為健壯性）。如果準(zhǔn)確性和健壯性都滿足，接下來，就要考慮最重要的一點(diǎn)：通過算法編寫的程序，運(yùn)行的效率怎么樣。
運(yùn)行效率體現(xiàn)在兩方面：
算法的運(yùn)行時(shí)間。（稱為“時(shí)間復(fù)雜度”）
運(yùn)行算法所需的內(nèi)存空間大小。（稱為“空間復(fù)雜度”）
好算法的標(biāo)準(zhǔn)就是：在符合算法本身的要求的基礎(chǔ)上，使用算法編寫的程序運(yùn)行的時(shí)間短，運(yùn)行過程中占用的內(nèi)存空間少，就可以稱這個(gè)算法是“好算法”。
描述
> 給定一個(gè)非空整數(shù)數(shù)組，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)兩次。找出那個(gè)只出現(xiàn)了一次的元素。
說明：你的算法應(yīng)該具有線性時(shí)間復(fù)雜度。 你可以不使用額外空間來實(shí)現(xiàn)嗎？
示例 1:輸入: [2,2,1] 輸出: 1
示例 2:輸入: [4,1,2,1,2] 輸出: 4
題解
思路
使用額外HashMap來存儲每一個(gè)數(shù)組元素，最后取出個(gè)數(shù)為1的那一個(gè)（看到題目，實(shí)在沒有啥好思路，這個(gè)方法運(yùn)行效率肯定非常低）
代碼實(shí)現(xiàn)
class Solution {
public int singleNumber(int[] nums) {
Map temp = new HashMap<>();
for (int i : nums) {
temp.put(i, temp.get(i) == null ? 1 : temp.get(i) + 1);
}
for (int i : nums) {
if (temp.get(i) == 1) {
return i;
}
}
return 0;
}
} 復(fù)雜度分析
時(shí)間復(fù)雜度：O(n+n) = O(n)。
for循環(huán)的時(shí)間復(fù)雜度是 O(n)。空間復(fù)雜度：O(n)。hashmap需要的空間跟nums中元素個(gè)數(shù)相等。
執(zhí)行結(jié)果
最優(yōu)解：位操作
思路
任何數(shù)與0異或?yàn)槠浔旧恚? ^ n => n
相同的數(shù)異或?yàn)?： n ^ n => 0
XOR（異或） 滿足交換律和結(jié)合律：a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b
所以我們只需要將所有的數(shù)進(jìn)行 XOR 操作，得到那個(gè)唯一的數(shù)字。
代碼實(shí)現(xiàn)
class Solution {
public int singleNumber(int[] nums) {
int result = 0;
for(int i : nums) {
result^=i;
}
return result;
}
}復(fù)雜度分析
時(shí)間復(fù)雜度：O(n)。只需要將nums元素遍歷一遍，所以時(shí)間復(fù)雜度為nums中元素的個(gè)數(shù)。
空間復(fù)雜度：O(1)。
執(zhí)行結(jié)果
上述內(nèi)容就是如何處理leetcode136只出現(xiàn)一次的數(shù)字，你們學(xué)到知識或技能了嗎？如果還想學(xué)到更多技能或者豐富自己的知識儲備，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。
本文名稱：如何處理leetcode136只出現(xiàn)一次的數(shù)字
網(wǎng)站鏈接：http://fisionsoft.com.cn/article/jgspdi.html
