Daha yüksək və ya aşağı nömrəni təxmin edin LeetCode Həlli

Problem bəyanat

Guess Number Higher və ya Lower LeetCode Həlli – Guess Game oynayırıq. Oyun aşağıdakı kimidir:

bir nömrə seçirəm 1 üçün n. Məcburiyyətindəsiniz hansı nömrəni təxmin edin seçdim.

Hər dəfə səhv təxmin etdiyiniz zaman mən sizə deyəcəyəm ki, mənim seçdiyim rəqəm sizin təxmininizdən çox və ya aşağıdır.

Siz əvvəlcədən müəyyən edilmiş API çağırırsınız int təxmin (int num), bu üç mümkün nəticəni qaytarır:

• -1: Sizin təxmininiz seçdiyim rəqəmdən daha yüksəkdir (yəni num > seçin).
•  1: Sizin təxmininiz seçdiyim rəqəmdən aşağıdır (yəni num < seçin).
•  0: sizin təxmininiz seçdiyim rəqəmə bərabərdir (yəni num == seçin).

Qayıtmaq seçdiyim nömrə.

Misal:

Test işi 1:

Input:

n = 10

seçin = 2

Çıxış:

2

Test işi 2:

Input:

n = 6

seçin = 4

Çıxış:

4

Üçün izah Daha yüksək və ya aşağı nömrəni təxmin edin LeetCode Həlli :

i) İlk sınaq işi üçün biz 2-ni seçdik ki, nəticə 2 olsun.

ii) İkinci sınaq işi üçün biz 4-ü seçdik ki, nəticə 4 olsun.

Yanaşma

Idea:

Burada xətti həll olduqca aydındır. -dən təkrarlaya bilərik 1 üçün n və hər bir nömrənin seçimə uyğun olub olmadığını yoxlayın. Lakin bu, xətti vaxt aparacaq. Zaman mürəkkəbliyi olacaq O (n).

Beləliklə, sual yaranır ki, biz vaxtın mürəkkəbliyini necə optimallaşdıra bilərik? Burada giriş çeşidlənmiş qaydadadır və hər bir təxmin üçün 3 seçimimiz var. Ya eynidir. Eynidirsə, geri qaytara bilərik nömrə. Əgər seçilmiş nömrədən azdırsa, onu diapazonda axtarmalıyıq [nömrə+1…n]. Əgər seçilmiş nömrədən böyükdürsə, onu diapazonda axtarmalıyıq [nömrə-1…n]. Burada hər təxmin üçün girişi yarıya qədər azaldırıq. Beləliklə, zaman mürəkkəbliyi olacaq O(daxil ol2â € <n). Prinsipcə, biz müraciət edə bilərik İkili axtarış burada.

İlk sınaq vəziyyətinə baxaq:

başla son seçim təxmin (seç)

1 10 5 -1

1 4 2 0 (nömrəmizi aldıq)

Kodu

Guess Number Higher və ya Aşağı LeetCode Həlli üçün Java Proqramı

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int start = 1, end = n;
        while(start<=end) {
          int pick = start+(end-start)/2;
          if(guess(pick)==0)
            return pick;
          else if(guess(pick)==1)
            start = pick+1;
          else
            end = pick-1;
        }
        return -1;
    }
}

Guess Number Higher və ya Aşağı LeetCode Həlli üçün C++ Proqramı

class Solution {
public:
    int guessNumber(int n) {
        int start = 1, end = n;
        while(start<=end) {
          int pick = start+(end-start)/2;
          if(guess(pick)==0)
            return pick;
          else if(guess(pick)==1)
            start = pick+1;
          else
            end = pick-1;
        }
        return -1;
    }
};

Daha yüksək və ya aşağı LeetCode Həlli Guess Number üçün mürəkkəblik təhlili

Zamanın mürəkkəbliyi

Burada hər bir təxmin üçün axtarış hissəmizi yarıya qədər azaldırıq. Beləliklə, zamanın mürəkkəbliyi O(daxil ol2â € <n).

Kosmik Mürəkkəblik

Burada heç bir istifadə etmirik əlavə yer. Kosmik mürəkkəblik belədir O (1).

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