Massiv LeetCode Həllində Bütün Dublikatları tapın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg Facebook google microsoftBaxılıb 36

Problem bəyanat

Problem, LeetCode Həllində Massivdə Bütün Dublikatları Tapın sizə ölçü massivi verildiyini bildirir n diapazondakı elementləri ehtiva edir [1,n]. Hər bir tam ədəd bir və ya iki dəfə görünə bilər və siz massivdə iki dəfə görünən bütün elementləri tapmalısınız.Massiv LeetCode Həllində Bütün Dublikatları tapınPin

Massivdə bütün dublikatları tapmaq üçün nümunələr LeetCode Həll

Test işi 1 –

Daxiletmə – [4, 3, 2, 7, 8, 2, 3, 1]

Çıxış – [2, 3]

Test işi 2 –

Giriş – [1, 1, 2]

Çıxış – [1]

Test işi 3 –

Giriş – [1]

Çıxış – []

Yanaşma

Fikir

  1. Sualda ilk tutmaq budur ki massivdə mövcud olan nömrələr 1-dən n daxil olmaqla, burada n massivin ölçüsüdür. Beləliklə, biz serialın indeksləri üzərində bəzi manipulyasiyalar edə bilərik.
  2. Test vəziyyətinə nəzər salın – [1, 2, 3, 4, 4]. Müvafiq indekslər 0, 1, 2, 3, 3 olacaq, yəni nums[i] - 1.
  3. Massivdən keçərkən həmin elementə uyğun olan indeksi qeyd edirik. İşarələməklə biz nəzərdə tuturuq nums[abs(nums[i])-1] = -1*nums[abs(nums[i])-1].
  4. Eyni keçiddə hansısa indeksdə mənfi elementlə qarşılaşırıqsa, bu o deməkdir ki, indeks artıq əvvəllər işarələnib və təkrarlanan element. Beləliklə, biz həmin elementi (indeksi) çıxış massivinə itələyirik.

bir element olarsa x massivdə yalnız bir dəfə baş verir, indeksdəki dəyər abs(x)-1 mənfi olur və sonrakı bütün təkrarlamalar üçün belə qalır.

  1. Massivdən keçin. Bir element görəndə x ilk dəfə olaraq indeksdəki dəyəri inkar edəcəyik abs(x)-1.
  2. Ancaq növbəti dəfə bir element gördükdə, biz deyil yenidən inkar etmək lazımdır! Əgər indeksdəki dəyər abs(x)-1 onsuz da mənfi, elementi gördüyümüzü bilirik x əvvəl.

Array LeetCode Həllində Bütün Dublikatları Tapmaq üçün kod

C + +

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> ans;
        int n = nums.size();
        for(int i=0;i<n;i++){
            if(nums[abs(nums[i])-1] < 0) ans.push_back(abs(nums[i]));
            nums[abs(nums[i])-1] = -1*nums[abs(nums[i])-1];
        }
        return ans;
    }
};

JAVA

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        int n = nums.length;
        for(int i=0;i<n;i++){
            if(nums[Math.abs(nums[i])-1] < 0) ans.add(Math.abs(nums[i]));
            nums[Math.abs(nums[i])-1] = -1*nums[Math.abs(nums[i])-1];
        }
        return ans;
    }
}

Python

class Solution(object):
    def findDuplicates(self, nums):
        ans = []
        for i in nums:
            if nums[abs(i)-1] < 0:
                ans.append(abs(i))
            nums[abs(i)-1] = -1*nums[abs(i)-1]
        return ans
        """
        :type nums: List[int]
        :rtype: List[int]
        """

Array LeetCode Həllində Bütün Dublikatları Tapmaq üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

Biz massivi yalnız bir dəfə keçdiyimiz üçün yanaşma üçün zaman mürəkkəbliyi O(n)-dir.

Kosmik Mürəkkəblik

Biz alqoritmdə heç bir köməkçi boşluqdan istifadə etmirik, ona görə də fəzanın mürəkkəbliyi O(1)-dir.

Translate »