Sorted Array II Leetcode Solution-dan Dublikatları silin

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Facebook google microsoft
Geyim İki işarəBaxılıb 54

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat :

Bir tam verilir array sıralanmış ədədlər azalmayan sifariş, bəzi dublikatları silin yerində belə ki, hər bir unikal element görünür ən çox iki dəfə. Bu nisbi qayda elementləri saxlanılmalıdır eyni.

Bəzi dillərdə massivin uzunluğunu dəyişmək mümkün olmadığından, bunun əvəzinə nəticəni xanaya yerləşdirməlisiniz. birinci hissəsi massiv nömrələri. Daha rəsmi olaraq, dublikatları sildikdən sonra k element varsa, onda ilk k ədəd elementləri yekun nəticəni saxlamalıdır. İlk k elementdən sonra nə buraxdığınızın əhəmiyyəti yoxdur.

Qayıdın k yekun nəticəni birinci yerə qoyduqdan sonra k yuvaları ədəd.

Do yox başqa massiv üçün əlavə yer ayırın. tərəfindən bunu etməlisiniz giriş massivinin dəyişdirilməsi yerində O(1) əlavə yaddaşla.

Xüsusi Hakim:

Hakim həllinizi aşağıdakı kodla yoxlayacaq:

int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

Bütün iddialar keçərsə, həlliniz olacaq qəbul.

Misal:

Məsələn 1 

Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Məsələn 2 

Input: nums = [0,0,1,1,1,1,2,3,3]
Output: 7, nums = [0,0,1,1,2,3,3,_,_]
Explanation: Your function should return k = 7, with the first seven elements of nums being 0, 0, 1, 1, 2, 3 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Məhdudiyyətlər:

1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums is sorted in non-decreasing order.

İntuisiya:

  • Massiv olduğundan sıralandı, bütün dublikatlar olacaq ardıcıl. Beləliklə, istifadə edə bilərik iki göstərici alqoritmi.
  • Bir göstərici nums massivini təkrarlayacaq, yəni itr və digəri yəni uzunluq eyni nums massivinin indeksinə işarə edəcək, lakin bu uzunluq indeksindən əvvəl ədədlərin bütün elementlərinin sayı 2-dən çox deyil.

Alqoritm:

  • Dəyişən uzunluq götürün və onu 0-cı indeksdəki elementlə işarələyin massiv nömrələri.
  • Dəyişən götürün countElement başlamaq bu ilə 1 çünki biz artıq qaçırıq 0-cı indeks.
  • Dəyişən götürün itrbaşlamaq bu ilə 1Kimi, itr təkrar edəcək nömrə.
  • If nums[itr]==nums[itr-1]countElement azdır 2 sonra elementləri qoya bilərik nums[itr] uzunluq vəziyyətində, qoyduqdan sonra artım uzunluq dəyişəni.
  • Digər halda nums[itr] !=nums[itr-1] onda nums[itr] yeni elementdir, belə ki, yenə bizim hesablama elementi olacaq  1-ə bərabərdir,
  • Nəhayət qayıdış uzunluq+1 dəyişən, uzunluq indeksi kimi işləyir və uzunluğu qaytarmalıyıq.
  • Daha yaxşı başa düşmək üçün kodu keçin

Sorted Array II-dən dublikatları silmək üçün kod:

Sorted Array II Leetcode Java Həllindən Dublikatları silin:

class Solution {
    public int removeDuplicates(int[] nums) {
        int n=nums.length;
        int itr=1;
        int length=0;
        int countElement =1;
        while(itr<n){
            if(nums[itr]==nums[itr-1]){
                if(countElement<2){
                    countElement++;
                    length++;
                    nums[length]=nums[itr];
                }  
            }
            else{
                countElement=1;
                length++;
                nums[length]=nums[itr];
            }
           itr++; 
        }
        return length+1;
    }
}

Sorted Array II Leetcode C++ Həllindən Dublikatları silin:

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
         int n=nums.size();
        int itr=1;
        int length=0;
        int countElement =1;
        while(itr<n){
            if(nums[itr]==nums[itr-1]){
                if(countElement<2){
                    countElement++;
                    length++;
                    nums[length]=nums[itr];
                }  
            }
            else{
                countElement=1;
                length++;
                nums[length]=nums[itr];
            }
           itr++; 
        }
        return length+1;
    }
};

Sorted Array II-dən Dublikatları Silmək üçün Mürəkkəblik Təhlili:

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (N) çünki biz N = giriş massivinin ölçüsü olduğu ən pis halda bütün giriş massivini bir dəfə keçirik.

Kosmik Mürəkkəblik 

Yuxarıdakı həllin Kosmik Mürəkkəbliyi O (1) istifadə etdiyimiz üçün daimi əlavə yer.

Crack Sistemi Dizayn Müsahibələri
Translate »