Nombor Tunggal I

Masalah

Kita kena cari nombor yang hadir sekali sahaja.
Pendekatan brute force ialah menggunakan HashMap untuk menjejaki kiraan nilai dan kemudian mengembalikan nilai yang mempunyai kiraan =1;

Pendekatan optimum menggunakan manipulasi bit:

Kami tahu bahawa 1^0 = 1, 0 ^1 = 1, 0 ^ 0 = 0 , 1 ^ 1= 0 untuk semua gabungan lain.
ia bermakna exor memberikan 0 untuk nilai yang sama oleh itu jika kita exor semua nilai dalam tatasusunan ia akan memberikan hanya nombor yang kiraan adalah 1( kerana nilai selebihnya akan bertukar 0)

TC: O(n)
SC: O(1)

class Solution {
    public int singleNumber(int[] nums) {
        int single = nums[0];
        for(int i =1;i<nums.length;i++){
            single = single^nums[i];
        }
        return single;
    }
}

Atas ialah kandungan terperinci Nombor Tunggal I. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!