BST Leetcode Həllində K-ci Ən Kiçik Element

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg Citadel eBay Facebook google LinkedIn microsoft Kahin Über VMwareBaxılıb 65

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

BST Leetcode Həllində K-ci Ən Kiçik Element – ​​Nəzərə alınmaqla root ikili axtarış ağacı və tam ədəd k, qayıt bu kth ən kiçik dəyər (1 indeksli) ağacdakı qovşaqların bütün dəyərlərindən.

Nümunələr:

BST Leetcode Həllində K-ci Ən Kiçik ElementPin

Input:

 root = [3,1,4,null,2], k = 1

Çıxış:

 1

 

BST Leetcode Həllində K-ci Ən Kiçik ElementPin

Input:

 root = [5,3,6,2,4,null,null,1], k = 3

Çıxış:

 3

Explanation:

Verilmiş BST-də 3-cü ən kiçik ədəd 3-dür, ona görə də 3-ü çıxarırıq.

Yanaşma

  • İkili ağac sıralanmış qaydada elementlərdən ibarətdir.
  • Həlli tapmağın ən asan yolu elementləri prioritet növbəyə daxil etmək və sonra k-1 elementlərini çıxarmaqdır, sonra prioritet növbənin yuxarı elementi ağacın k-ci ən kiçik elementidir.
  • Optimallaşdırılmış həll sıra ilə keçid edir və ziyarət edilən elementlərin sayının hesabını aparır.
  •  İkili ağacın ən sol elementini ziyarət etdikdən sonra, saymanı 1-ə qədər artırın və ardıcıllıqla geri dönün və sayı artırın.
  • Say k-yə çatdıqda həmin elementi qaytarın.

Idea:

Fikir BST-dən keçin nizam moda, BST-nin sıra keçidi artan ardıcıllıqla sıralandığı üçün biz edə bilərik hər dəfə bu say k-yə bərabər olduqda, bir hesab saxlamaq, biz K-ci ən kiçik elementimizi tapdıq, ona görə də onu qaytarırıq.

BST-ni sıradan bir keçidlə keçmək üçün, yığından istifadə edə bilərik. Əvvəlcə hər bir nodu yığına daxil edərək ən soldakı qovşaqdan keçirik ki, biz null tapana qədər, sonra yığından elementləri bir-bir çıxarırıq və həmin qovşağın sağına keçirik.

BST-də K-ci Ən Kiçik Element üçün Kod

C ++ kodu

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        
        stack<TreeNode*> st;
        // stack to store the node pointers.
        
        while(true){
            
            while(root!=NULL){
                st.push(root);
                root = root->left;
            }
            // traversing to the leftmost of a node and inserting it into stack.
            root = st.top();
            st.pop();
            k--;
            if(k==0){
                // if its Kth smallest then return it.
                return root->val;
            }
            
            root = root->right;
            //move to the next largest node which is at the right in BST.
        }
        
    }
};

Java kodu

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        LinkedList<TreeNode> st = new LinkedList<>();
        // stack to store the node pointers.
        
        while(true){
            
            while(root!=null){
                st.push(root);
                root = root.left;
            }
            // traversing to the leftmost of a node and inserting it into stack.
            root = st.pop();
            k--;
            if(k==0){
                // if its Kth smallest then return it.
                return root.val;
            }
            
            root = root.right;
            //move to the next largest node which is at the right in BST.
        }
    }
}

BST Leetcode Həllində K-ci Ən Kiçik Element üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

Zaman mürəkkəbliyi O(H+k), burada H ağacın hündürlüyüdür, çünki yığından elementləri çıxarmazdan əvvəl yarpaq düyününə gedirik və sonra elementləri açmağa başlayırıq, buna görə də ümumi vaxt mürəkkəbliyi O(logn) yarpaq düyününə qədər getmək üçün, və əlavə O(k) K-ci ən kiçik elementi tapmaq vaxtı. Ümumi zaman mürəkkəbliyi O (logn + k) üçün balanslı ağacO(N + k) üçün bu Əyilmiş ağac.

Kosmik Mürəkkəblik

Biz xarici məkandan istifadə edirik, yəni qalaq, istənilən vaxt ağacın hündürlüyündən çox elementlərin sayı olmayacaq, Beləliklə, ümumi fəzanın mürəkkəbliyi O(H).

 

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