Tək Nömrəli Leetcode Həlli

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic Airbnb Amazon alma Atlassian Bloomberg Facebook google microsoft Palantir Texnologiyaları SAP TCS cuqquldamaq Über Yahoo ZohoBaxılıb 40

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

Referans: https://en.wikipedia.org/wiki/Exclusive_or

Translate »