Mündəricat
Problem bəyanat
Tək Nömrəli Leetcode Həlli – Bizə boş olmayan tam ədədlər massivi verilir və tam bir dəfə görünən elementi tapmaq lazımdır. Sualda verilir ki, bir elementdən başqa hər bir element iki dəfə görünür.
Misal 1:
Input: nums = [2,2,1] Output: 1
Misal 2:
Input: nums = [4,1,2,1,2] Output: 4
Misal 3:
Input: nums = [1] Output: 1
Tək Nömrəli Leetcode Həlli üçün izahat:
Birincidə məsələn. 1 dəqiq bir dəfə görünür, lakin 2 iki dəfə görünür, cavab 1-dir
İkincidə məsələn. 1 və 2 iki dəfə görünür və buna görə də cavab 4-dür.
Finalda məsələn. 1 yalnız bir dəfə görünür, ona görə də cavab 1-dir
Yanaşma
Idea:
Heç bir məhdudiyyət olmasaydı, bu sual çox asandır vaxt və məkan mürəkkəblik.
Hələlik fərz edək ki, heç bir məhdudiyyət yoxdur.
Bu vəziyyətdə bu sualı həll etməyin bir neçə yolu var.
- Hashmap saxlaya və onların sayını saya bilərik bir element görünür. Hashmap-də bir dövrə işlədə və 1 sayı olan elementi çap edə bilərik.
- Biz elementləri sıralayın və a[i] ≠ a[i-1] & a[i]≠ a[i+1] (birinci və sonuncu elementə diqqət yetirdiyimizi fərz etsək), n massivinin ölçüsündə i üçün yoxlayın və a[ çap edin. mən]
Sabit yaddaş və ölçüdən istifadə etməli olduğumuz üçün birinci və ikinci həlləri atırıq.
Verilmiş məhdudiyyətdən sonra bu problemi həll etməyin yeganə yolu XOR konsepsiyasından istifadə etməkdir.
Anlayış
- XOR sıfır və bəzi bit həmin biti qaytarır
- a ^ 0 = a
- İki eyni bitin XOR-u 0 qaytarır
- a^a = 0
- Bəzi a və b bitləri üçün a^b^a-nın XOR b qaytarır
- a^b^a = (a^a)^b = 0^b = b
Beləliklə, biz unikal nömrə tapmaq üçün bütün bitləri birlikdə XOR edə bilərik.
Kodu
Tək Nömrəli C++ Proqramı:
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for(int x: nums) {
res ^= x;
}
return res;
}
};
Tək Nömrəli Java Proqramı:
class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for (int x : nums) {
res ^= x;
}
return res;
}
}
Tək Nömrəli Python Proqramı:
class Solution(object):
def singleNumber(self, nums):
res = 0
for x in nums:
res ^= x
return res
Tək Nömrəli Leetcode Həlli üçün Mürəkkəblik Təhlili
- Zamanın mürəkkəbliyi: O(n).
- Biz yalnız nömrələr massivində təkrarlandıq, ona görə də vaxt mürəkkəbliyi verilmiş massivdəki elementlərin sayıdır.
- Kosmik mürəkkəblik: O (1)
- No. əlavə yer cavabı saxlamaq üçün res dəyişənindən başqa istifadə olunur
