Massiv Cütlüklərinin k LeetCode Həlli ilə Bölünmədiyini Yoxlayın

Problem bəyanat

Massiv Cütlüklərinin k-yə Bölünmədiyini Yoxlayın.

Biz massivi tam olaraq n/2 cütlərinə bölmək istəyirik ki, hər bir cütün cəmi k-ə bölünsün.

Doğru qayıdın  Bunu etmək üçün bir yol tapa bilsəniz və ya saxta əksinə.

Massiv cütlərinin k-yə bölündüyünü yoxlamaq üçün nümunə LeetCode Həlli:

Test işi 1:

Input:

inputArr = [1, 2, 3, 4, 5, 10, 6, 7, 8, 9],

k = 5

Çıxış:

doğru

Test işi 2:

inputArr = [-1, 1, -2, 2, -3, 3, -4, 4]
k = 3

Çıxış:

doğru

Test işi 3:

inputArr = [1, 2, 3, 4, 5, 6]
k = 10

Çıxış:

saxta

Massiv cütlərinin k-yə bölündüyünü yoxlamaq üçün izahat LeetCode Həlli:

i) Birinci sınaq işi üçün onları (1, 9), (2, 8), (3, 7), (4, 6) və (5, 10) kimi cütlərə bölmək olar. The Bu cütlərin hər birinin cəmi 5-ə bölünür. Beləliklə, nəticə doğrudur.

ii) İkinci sınaq işi üçün onları (-1, 1), (-2, 2), (-3, 3) və (-4, 4) kimi cütlərə bölmək olar. Bu cütlərin hər birinin cəmi 3-ə bölünür. Beləliklə, nəticə doğrudur.

iii) Üçüncü sınaq işi üçün, biz bölmək üçün heç bir yol yoxdur cəmi kimi cütlərə verilmiş massiv hər bir cüt 10-a bölünür. Beləliklə, nəticə yalançıdır.

Yanaşma

Idea:

2 ədəd 'a' və 'b' verilmişdir:
If a % k == x və b % k == k – x :
sonra (a + b) k-ə bölünür

1) Əsas ideya verilmiş massivin bütün elementlərinin qalıqlarının sayını saxlamaqdır.

2) Tutaq ki, biz saxladıq dakı tezliklər modtezlik array. qalan 0 elementin bölünə biləcəyini bildirir k. Belə ki modtezlik[0] bölünə bilən bütün elementlərin hesabını aparır k. Bir element bölünürsə k, o, başqa elementlə yalnız və yalnız bölünə bildiyi halda qoşa yarada bilər k əks halda cəmi bölünməyəcək k. Belə ki modtezlik[0] bərabər olmalıdır.

3) Qalanları olan hər bir element üçün i (i != 0) qalığı olan element olmalıdır ki. Deməli, modtezlik[I] bərabər olmalıdır modtezlik[ki] .

4) Yuxarıdakı şərtlərdən hər hansı biri uyğun gəlmirsə, geri qayıda bilərik yanlış, yoxsa biz qayıdacağıq doğru.

Kodu

Massiv Cütlərinin k-ə bölündüyünü yoxlamaq üçün Java proqramı

class Solution {
    public boolean canArrange(int[] arr, int k) {
        int[] modFrequency = new int[k];
        for(int num : arr){
            num %= k;
            if (num < 0) 
                num += k;
            modFrequency[num]++;
        }
        if(modFrequency[0] % 2 != 0) 
            return false;
        
        for(int i = 1; i <= k/2; i++)
            if(modFrequency[i] != modFrequency[k-i]) 
                 return false;
      
        return true;
    }
}

Massiv Cütlərinin k-ə bölündüyünü yoxlamaq üçün C++ proqramı

class Solution {
public:
    bool canArrange(vector<int>& arr, int k) {
        map<int, int> modFrequency;
        for (int i = 0; i < arr.size(); ++i)
        {
            int num = arr[i] % k;
            if (num < 0)
                num += k;
            modFrequency[num]++;
        }
        if (modFrequency[0] % 2 != 0)
            return false;
        for (int i = 1; i <= k / 2; i++)
        {
            if (modFrequency[i] != modFrequency[k - i])
                return false;
        }
        return true;
    }
};

Massiv cütlərinin k LeetCode Həlli ilə Bölünmədiyini Yoxlamaq üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

Burada biz bir dəfə massivdən keçirik. Massivin ölçüsü n olarsa, götürəcəkdir O (n) vaxt. üçün başqa bir döngədən istifadə edirik k/2 dəfə. aparacaq O(k/2) və ya O(k) vaxt. Beləliklə, yuxarıdakı kodun zaman mürəkkəbliyi əsasəndir Maks(O(n), O(k)).

if n > k/2, Zaman mürəkkəbliyi = O(n)

daha Zaman mürəkkəbliyi = O(k/2) ≡ O(k)

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi Tamam) çünki biz tezlikləri saxlamaq üçün xəritə və ya massivdən istifadə edirik.

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