leetcode136：只出现一次的数字

题目链接

leetcode

题目描述

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
设计并实现线性时间复杂度 O(n) 的算法来解决此问题，且该算法只使用常量额外空间 O(1)。

C++ 代码

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

void printArray(const vector<int>& arr) {
    for (const int& num : arr) {
        cout << num << " ";
    }
    cout << endl;
}

/*
    哈希表

    时间复杂度：O(n)
        其中 n 是数组的长度。
        遍历整个数组来填充哈希表，然后再遍历哈希表来找到只出现一次的数字。
        每个遍历操作都是线性的，所以总的时间复杂度是 O(n)。
    空间复杂度：O(n)
        存储数组中的每个不同数字在哈希表中，所以空间复杂度是 O(n)。
*/
class Solution_0 {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> num2cnt;
        for (const int& num : nums) {
            num2cnt[num]++;
        }
        for (const auto& pair : num2cnt) {
            if (pair.second == 1) {
                return pair.first;
            }
        }
        
        return -1; // 若没找到只出现一次的数字，则返回-1
    }
};

/*
    任何数和 0 做异或运算，结果仍是原来的数。
    任何数和其自身做异或运算，结果是 0。
    
    时间复杂度：O(n)
        其中 n 是数组长度，只需要对数组遍历一次。
    空间复杂度：O(1)
*/
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (const int& num : nums) {
            res ^= num;
        }

        return res;
    }
};

int main() {
    Solution solution;
    vector<vector<int>> test_cases = {
        {2,2,1},
        {4,1,2,1,2},
        {1}
    };
    
    for (auto& nums : test_cases) {
        cout << "Input: ";
        printArray(nums);
        cout << "Output: " << solution.singleNumber(nums) << endl;
    }

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
   异或运算：
       初始化结果 result 为 0。
       遍历数组中的每个数字，将每个数字与 result 进行异或运算。
       由于异或运算的性质，成对出现的数字最终会抵消为 0，而只出现一次的数字会保留下来。
   边界条件：
       如果数组中只有一个数字，直接返回该数字。

   时间复杂度：O(n)
       遍历一次数组，时间复杂度为 O(n)，其中 n 是数组的长度。
   空间复杂度：O(1)
       使用了一个变量 result，空间复杂度为 O(1)。
*/
// singleNumber 返回数组中只出现一次的数字
func singleNumber(nums []int) int {
	result := 0
	for _, num := range nums {
		result ^= num
	}
	return result
}

func main() {
	// 测试用例
	testCases := []struct {
		nums    []int
		expected int
	}{
		{
			nums:    []int{2, 2, 1},
			expected: 1,
		},
		{
			nums:    []int{4, 1, 2, 1, 2},
			expected: 4,
		},
		{
			nums:    []int{1},
			expected: 1,
		},
	}

	for i, tc := range testCases {
		result := singleNumber(tc.nums)
		fmt.Printf("Test Case %d, Input: nums = %v\n", i+1, tc.nums)

		if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %d, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %d, FAIL (Expected: %d)\n", i+1, result, tc.expected)
		}
	}
}