136. Single Number

Problem

Bài toán yêu cầu tìm phần tử duy nhất xuất hiện một lần trong mảng số nguyên, trong khi các phần tử khác đều xuất hiện đúng hai lần.

Approach - XOR

Tính chất: a ^ a = 0, a ^ 0 = a. Phép XOR là giao hoán và kết hợp

Khi XOR tất cả các phần tử trong mảng, các cặp số giống nhau sẽ triệt tiêu lẫn nhau, chỉ còn lại số lân xuất hiện một lần

Đây là cách tối ưu nhất, vừa đạt TC: O(n), vừa dùng SC: O(1)

Solution

typescripttypescript

1function singleNumber(nums: number[]): number {
2    let res = 0
3    for(const num of nums) res = res ^ num
4    return res
5};

Loading content...