一、題目描述與要求

136. 只出現(xiàn)一次的數(shù)字 - 力扣（LeetCode）

題目描述

給你一個 非空 整數(shù)數(shù)組 nums ，除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)兩次。找出那個只出現(xiàn)了一次的元素。

你必須設計并實現(xiàn)線性時間復雜度的算法來解決此問題，且該算法只使用常量額外空間。

示例

示例1：

輸入：nums = [2,2,1]
輸出：1

示例2：

輸入：nums = [4,1,2,1,2]
輸出：4

示例3：

輸入：nums = [1]
輸出：1

提示

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• 除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)兩次。

二、解題思路

總的思路：

? ? ? ?首先分析題目，題目要求是找出數(shù)組中只出現(xiàn)了一次的數(shù)字，因此我們需要思考怎么找出這一個數(shù)字。且題目要求了只能使用常量額外空間，也就是說不能利用數(shù)組等多個空間的變量來解決問題。同時時間復雜度也要是線性的。

? ? ? ? 最簡單的方法就是統(tǒng)計每個數(shù)字出現(xiàn)的次數(shù)（題目規(guī)定了其他數(shù)字只出現(xiàn)兩次），將數(shù)組中的數(shù)字與除它以外數(shù)組的每一個元素進行比較，相同則次數(shù)增加，遍歷比較完后判斷次數(shù)是否為1，如果為1則將這一數(shù)字賦值給result。重復以上步驟直至遍歷完整個數(shù)組?！咀顦闼氐膶崿F(xiàn)方法，但是會超時。時間復雜度O（n2）空間復雜度為O（1）】

? ? ? ?另一個方法則是需要利用位運算中的異或運算來找出只出現(xiàn)了一次的數(shù)字。a⊕0=a。a⊕a=0。a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。因此可以將數(shù)組第一個值賦值給result，然后將result與數(shù)組中的元素以此進行異或運算，最后就能得到目標數(shù)字?！拘枰獙ξ贿\算性質(zhì)熟悉】

具體步驟：

嵌套循環(huán)遍歷方法：

①定義輔助變量result與count，result初值隨便定義，count在第一層for循環(huán)中定義初值為1

②for循環(huán)嵌套for循環(huán)，將數(shù)組中的數(shù)字與除它以外數(shù)組的每一個元素進行比較，判斷次數(shù)是否為1，如果為1則將這一數(shù)字賦值給result。

③返回result文章來源地址http://www.zghlxwxcb.cn/news/detail-532778.html

異或運算方法：

①定義輔助變量result=nums[0]

②利用for循環(huán)遍歷數(shù)組，將result與數(shù)組的每個元素進行異或運算并保存結果

③返回result

三、具體代碼【C語言】

①嵌套循環(huán)遍歷方法：【時間O(n2) 空間O(1) 】leetcode提交超時

int singleNumber(int* nums, int numsSize) {
    if (numsSize == 1)  return nums[0];//如果數(shù)組只有一位的話則直接輸出
    int result = 0;
    int count;
    //遍歷整個數(shù)組，統(tǒng)計出現(xiàn)次數(shù)
    for (int i = 0; i < numsSize; i++) {
        count = 1;
        for (int j = 0; j < numsSize; j++) {
            if (j != i) {
                if (nums[i] == nums[j]) {
                    ++count;//有重復的，次數(shù)+1
                }
            }
        }
        if (count == 1)//只出現(xiàn)一次
        {
            result = nums[i];
        }
    }
    return result;
}

②異或運算方法：【時間O(n) 空間O(1) 】

int singleNumber(int* nums, int numsSize){
    if (numsSize == 1)  return nums[0];//如果數(shù)組只有一位的話則直接輸出
    int result = nums[0];
    //遍歷整個數(shù)組
    for (int i = 1; i < numsSize; i++) {
        result^=nums[i];
    }
    return result;
}

到了這里，關于2023年7月3日leetcode每日一題打卡——136.只出現(xiàn)一次的數(shù)字的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！