Peak Element II LeetCode Həllini tapın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Facebook google HRT microsoft
XingBaxılıb 60

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 tapın Pik Element II LeetCode Həlli – A pik 2D şəbəkəsindəki element elə bir elementdir ciddi şəkildə daha böyükdür hamısından daha çox bitişik sol, sağ, yuxarı və aşağı qonşular.

Verilmiş a 0 indeksli m x n matris mat hara heç bir iki qonşu hüceyrə bərabər deyiltapmaq hər pik element mat[i][j] və qayıt uzunluq 2 massivi [i,j].

Bütün matrisin bir ilə əhatə olunduğunu güman edə bilərsiniz xarici perimetr dəyəri ilə -1 hər hüceyrədə.

Siz daxil olan bir alqoritm yazmalısınız O(m log(n)) or O(n log(m)) vaxt.

Peak Element II LeetCode Həllini tapınPin

Input: mat = [[1,4],[3,2]]
Output: [0,1]
Explanation: Both 3 and 4 are peak elements so [1,0] and [0,1] are both acceptable answers.

Izahat

bağışlamaq matrix[M][N], yeni 1D massivi yaradın maxPlaneOfCol[N] hər bir sütunda ən böyük rəqəmi saxlayır.

Yuxarıdakı matris üçün, maxPlaneOfCol = {4, 9, 6, 3, 7, 5}
Qoy maxPlaneOfCol[i] təyyarənin hündürlüyünü indeksdə təmsil edir i

İndi biz 2D problemini 1D probleminə endirmişik. Zirvə Elementini Tap-da olduğu kimi eyni məntiqdən istifadə edərək, pik müstəvisi olan sütunu tapa bilərik. Unutmayın, elementlər maxPlaneOfCol hər sütunun ən böyük sayını təmsil edir. Əgər indeksdə pik müstəvisi tapsaq, deməli, element var  column# p bu, bütün elementlərdən daha böyükdür column# p-1 və column# p+1. Pik sütununu əldə etdikdən sonra onu asanlıqla tapa bilərik row# pik element column# p. İndi hər ikiniz var row# və col# 2D massivindəki pik elementin. Bu belədir !!

Yerləşdirmək maxPlaneOfCol[N], biz 2D massivindəki bütün sütunları keçməliyik, bu, əsasən o deməkdir ki, biz 2D massivindəki bütün elementləri oxumalıyıq. Beləliklə, siz bütün 2D massivini oxuyarkən niyə 2D massivindəki ən böyük rəqəmin koordinatlarını qaytarmayasınız?!! Ən böyük elementin pik element olacağına zəmanət verilir, elə deyilmi !!??

Biz həqiqətən tapmaq lazımdır max hər sütunda? Yalnız tapmaq kifayət etməyəcək max Bu midColumn ? tapsaq max yalnız midColumn, hesablayacağıq max yalnız log(N) bütün alqoritmimizdəki sütunlar.

Kodu

Pik Elementi Tapmaq üçün C++ Kodu II

class Solution {
public:
    vector<int> findPeakGrid(vector<vector<int>>& mat) {
        int startCol = 0, endCol = mat[0].size()-1;
        
        while(startCol <= endCol){
            int maxRow = 0, midCol = startCol + (endCol-startCol)/2;
            
            for(int row=0; row<mat.size(); row++){
                maxRow = mat[row][midCol] >= mat[maxRow][midCol]? row : maxRow;   
            }
            
            bool leftIsBig    =   midCol-1 >= startCol  &&  mat[maxRow][midCol-1] > mat[maxRow][midCol];
            bool rightIsBig   =   midCol+1 <= endCol    &&  mat[maxRow][midCol+1] > mat[maxRow][midCol];
            
            if(!leftIsBig && !rightIsBig)          // we have found the peak element
                return vector<int>{ maxRow, midCol};
            
            else if(rightIsBig) // if rightIsBig, then there is an element in 'right' that is bigger than all the elements in the 'midCol', 
                startCol = midCol+1;    //so 'midCol' cannot have a 'peakPlane'
            
            else // leftIsBig
                endCol = midCol-1;
        }
        return vector<int>{-1,-1};
    }
};

Pik elementi tapmaq üçün Java kodu II

class Solution {
    public int[] findPeakGrid(int[][] mat) {
        int startCol = 0, endCol = mat[0].length-1;
        
        while(startCol <= endCol){
            int maxRow = 0, midCol = startCol + (endCol-startCol)/2;
            
            for(int row=0; row<mat.length; row++){
                 maxRow = mat[row][midCol] >= mat[maxRow][midCol]? row : maxRow;  
            }
            
            boolean leftIsBig    =   midCol-1 >= startCol  &&  mat[maxRow][midCol-1] > mat[maxRow][midCol];
            boolean rightIsBig   =   midCol+1 <= endCol    &&  mat[maxRow][midCol+1] > mat[maxRow][midCol];
            
            if(!leftIsBig && !rightIsBig)   // we have found the peak element
                return new int[]{maxRow, midCol};
            
            else if(rightIsBig)  // if rightIsBig, then there is an element in 'right' that is bigger than all the elements in the 'midCol', 
                startCol = midCol+1; //so 'midCol' cannot have a 'peakPlane'
            
            else // leftIsBig
                endCol = midCol-1;
        }
        return null;
    }
}

Pik Elementi Tapmaq üçün Python Kodu II

class Solution(object):
    def findPeakGrid(self, mat):
        startCol = 0
        endCol = len(mat[0])-1
       
        while startCol <= endCol:
            maxRow = 0
            midCol = (endCol+startCol)//2
            
            for row in range(len(mat)):
                maxRow = row if (mat[row][midCol] >= mat[maxRow][midCol]) else maxRow
            
            leftIsBig    =   midCol-1 >= startCol  and  mat[maxRow][midCol-1] > mat[maxRow][midCol]
            rightIsBig   =   midCol+1 <= endCol    and  mat[maxRow][midCol+1] > mat[maxRow][midCol]
            
            if (not leftIsBig) and (not rightIsBig):   # we have found the peak element
                return [maxRow, midCol]
            elif rightIsBig:             # if rightIsBig, then there is an element in 'right' that is bigger than all the elements in the 'midCol', 
                startCol = midCol+1     # so 'midCol' cannot have 'peakPlane'
            else:                           # leftIsBig
                endCol = midCol-1
                
        return []

Pik Element II LeetCode Həllinin Tapılması üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

O(M*Uzun N)

Kosmik Mürəkkəblik

O(1) çünki biz heç bir əlavə yerdən istifadə etmirik.

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