Maksimum sürüşmə pəncərə

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Paytaxt Akuna Amazon ByteDance Citadel Verilənlər bazası Dropbox Expedia Facebook google IBM Über
Dequeue Yığın Sürüşmə pəncərəBaxılıb 68

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.

In Maksimum sürüşmə pəncərə problem verdik array nums, k ölçülü hər bitişik pəncərə üçün pəncərədə maksimum elementi tapın.

misal

Input
nums [] = {1,3, -1, -3,5,3,6,7} k = 3
Buraxılış
3,3,5,5,6,7 {}

Izahat
Maksimum sürüşmə pəncərəPin

Maksimum sürüşən pəncərə üçün sadəlövh yanaşma

K ölçülü hər bitişik pəncərə üçün pəncərədən keçin və maksimum elementi tapın.

  1. İndeks 0-dan bir döngə işlədin (massivin ölçüsü - k - 1)
  2. İndeksdən (i + k) başqa bir iç içə döngə işlədin
  3. İç içə dönmə bir pəncərəni təmsil edir, iç içə döngənin içərisində maksimum dəyəri tapın
  4. Yuxarıda tapılan maksimum dəyər cari pəncərənin maksimum dəyəridir.
  5. Bütün maksimumları tapmaq üçün yuxarıdakı addımları təkrarlayın

Zaman Mürəkkəbliyi = O (n * k)
Kosmik Mürəkkəblik = O (1)

JAVA Kodu

public class Naive {
    private static int[] maxSlidingWindow(int[] nums, int k) {
        int ans[] = new int[nums.length - k + 1];
        // Traverse all the windows one by one
        for (int i = 0; i < nums.length - k + 1; i++) {
            // Initialise max as -infinite
            int max = Integer.MIN_VALUE;
            // Traverse the current window and find the maximum
            for (int j = i; j < i + k; j++) {
                max = Math.max(max, nums[j]);
            }
            // assign the current ans as maximum
            ans[i] = max;
        }
        return ans;
    }

    public static void main(String[] args) {
        // Example
        int nums[] = new int[]{1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        int max[] = maxSlidingWindow(nums, k);
        // Print the maximums
        for (int i = 0; i < max.length; i++) {
            System.out.print(max[i] + " ");
        }
    }
}
3 3 5 5 6 7

C ++ kodu

#include<bits/stdc++.h> 
using namespace std;

vector<int> maxSlidingWindow(int *nums, int k, int n) {
    vector<int> ans;
    // Traverse all the windows one by one
    for (int i = 0; i < n - k + 1; i++) {
        // Initialise max as -infinite
        int max = INT_MIN;
        // Traverse the current window and find the maximum
        for (int j = i; j < i + k; j++) {
            max = std::max(max, nums[j]);
        }
        // assign the current ans as maximum
        ans.push_back(max);
    }
    return ans;
}

int main() {
    // Example
    int nums[] = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    vector<int> ans = maxSlidingWindow(nums, k, sizeof(nums) / sizeof(nums[0]));
    // Print the maximums
    for (int i = 0; i < ans.size(); i++) {
        cout<<ans[i]<<" ";
    }
    return 0;
}
3 3 5 5 6 7

Maksimum sürüşmə pəncərəsi üçün optimal yanaşma

İlk k elementlərini özünüzü balanslaşdıran BST-də saxlayın, BST-də ən böyük element ilk pəncərə üçün maksimum element verir.
Qalan alt cədvəllər üçün əvvəlki pəncərənin ilk elementini öz balanslaşdırma BST-dən çıxarın və cari elementi əlavə edin, ən böyük element yenidən cari pəncərədəki maksimum elementi qaytarır.
Təkrarlanan elementlərin işini idarə etmək üçün BST-də elementə nisbətən tezliyi saxlayın.

Zaman Mürəkkəbliyi = O (n log (k))
Kosmik Mürəkkəblik = Tamam)

JAVA Kodu

import java.util.TreeMap;

public class Optimal {
    private static int[] maxSlidingWindow(int[] nums, int k) {
        int ans[] = new int[nums.length - k + 1];
        TreeMap<Integer, Integer> map = new TreeMap<>();
        // Store the first k elements and their frequencies in a self balancing BST
        for (int i = 0; i < k; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i]) + 1);
            } else {
                map.put(nums[i], 1);
            }
        }
        // Largest value of BST gives the first maximum
        ans[0] = map.lastKey();
        int index = 1;
        // Traverse the remaining elements
        for (int i = k; i < nums.length; i++) {
            // Remove first element of previous window from BST
            int freq = map.get(nums[i - k]);
            if (freq == 1) {
                map.remove(nums[i - k]);
            } else {
                map.put(nums[i - k], freq - 1);
            }
            
            // Add current element to BST
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i]) + 1);
            } else {
                map.put(nums[i], 1);
            }
            
            // Current asnwer is maximum value in BST
            ans[index++] = map.lastKey();
        }
        
        return ans;
    }

    public static void main(String[] args) {
        // Example
        int nums[] = new int[]{1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        int max[] = maxSlidingWindow(nums, k);
        // Print the maximums
        for (int i = 0; i < max.length; i++) {
            System.out.print(max[i] + " ");
        }
    }
}
3 3 5 5 6 7

C ++ kodu

#include<bits/stdc++.h> 
using namespace std;

vector<int> maxSlidingWindow(int *nums, int k, int n) {
    vector<int> ans;
    map<int, int> eleFreq;
    // Store the first k elements and their frequencies in a self balancing BST
    for (int i = 0; i < k; i++) {
        std::map<int, int>::iterator itr;
        itr = eleFreq.find(nums[i]);
        if (itr == eleFreq.end()) {
            eleFreq.insert(make_pair(nums[i], 1));
        } else {
            itr->second++;
        }
    }
    ans.push_back(eleFreq.rbegin()->first);
    for (int i = k; i < n; i++) {
        // Remove first element of previous window from BST
        std::map<int, int>::iterator itr = eleFreq.find(nums[i - k]);
        if (itr->second > 1) {
            itr->second--;
        } else {
            eleFreq.erase(itr->first);
        }
        
        // Add current element to BST
        itr = eleFreq.find(nums[i]);
        if (itr == eleFreq.end()) {
            eleFreq.insert(make_pair(nums[i], 1));
        } else {
            itr->second++;
        }
        
        // Current answer is maximum value in BST
        ans.push_back(eleFreq.rbegin()->first);
    }
    return ans;
}

int main() {
    // Example
    int nums[] = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    vector<int> ans = maxSlidingWindow(nums, k, sizeof(nums) / sizeof(nums[0]));
    // Print the maximums
    for (int i = 0; i < ans.size(); i++) {
        cout<<ans[i]<<" ";
    }
    return 0;
}
3 3 5 5 6 7

References

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