Leetcode 217. Yinelenen İçeriyor. DSA – #4

In: Genel


piton || C++ || TypeScript


Kaba Kuvvet Yaklaşımı

Bu yaklaşım çok basit, bu yüzden bu yaklaşımla fazla zaman kaybetmeyeceğim.

  • Bir element alıyoruz ve onu diğer tüm elementlerle karşılaştırıyoruz.
  • Bunu tüm elementler için yapıyoruz.


kod

def containsDuplicateMethod1(nums: list[int]) -> bool:
    length = len(nums)
    for i in range(length):
        for j in range(i + 1, length):
            if nums[i] == nums[j]:
                return True
    return False
Tam ekran moduna girinTam ekran modundan çık

Zaman Karmaşıklığı: O(n^2)
Uzay Karmaşıklığı: O(1)


Sıralamayı Kullanarak Daha İyi Yaklaşım

Yinelenen öğeleri bulmamız gerektiğinden, diziyi sıralayabilir ve sonra yinelenen öğeleri bulabiliriz.
Yinelenen öğeler birbirine bitişik olacaktır.

Örneğin: nums = [1, 2, 3, 1]

Sıralamadan sonra: nums = [1, 1, 2, 3]

Şimdi bitişik öğeleri karşılaştırarak yinelenen öğeleri bulabiliriz.


kod

def containsDuplicateMethod2(nums: list[int]) -> bool:
    nums.sort()
    length = len(nums)
    for i in range(length - 1):
        if nums[i] == nums[i + 1]:
            return True
    return False
Tam ekran moduna girinTam ekran modundan çık

Zaman Karmaşıklığı: O(nlogn)
Uzay Karmaşıklığı: O(1)


Hashing Kullanan En İyi Yaklaşım

Bu yöntemin anlaşılması da oldukça kolaydır.

  • Bir Set oluşturuyoruz.
  • Diziyi geçiyoruz ve öğenin Set’te olup olmadığını kontrol ediyoruz.
  • Öğe Küme’de mevcutsa, True değerini döndürürüz.
  • Eleman Küme’de yoksa, öğeyi Küme’ye ekleriz.
  • Tüm diziyi geçersek ve yinelenen herhangi bir öğe bulamazsak, False değerini döndürürüz.


kod

def containsDuplicateMethod3(nums: list[int]) -> bool:
    storage = set()
    for value in nums:
        if value in storage:
            return True
        storage.add(value)

    return False
Tam ekran moduna girinTam ekran modundan çık

Zaman Karmaşıklığı: O(n)
Uzay Karmaşıklığı: O(n)


Bonus


Hashing Kullanan En İyi Yaklaşım (tek astar)

def containsDuplicateMethod4(nums: list[int]) -> bool:
    return len(nums) != len(set(nums))
Tam ekran moduna girinTam ekran modundan çık

Bir cevap yazın

Ready to Grow Your Business?

We Serve our Clients’ Best Interests with the Best Marketing Solutions. Find out More

How Can We Help You?

Need to bounce off ideas for an upcoming project or digital campaign? Looking to transform your business with the implementation of full potential digital marketing?

For any career inquiries, please visit our careers page here.
[contact-form-7 404 "Bulunamadı"]