Artan və sonra Azalan Bir Dizidəki Maksimum Element

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon Goldman Sachs microsoft Paytm
GeyimBaxılıb 409

Problem bəyanat

N elementi olan verilmiş massivdə. Elementlər elə saxlanılır ki, əvvəlcə k elementləri artan qaydada, sonra nk elementləri oradan azalaraq, maksimum elementi tapmaq lazımdır array.

misal

a) Giriş massivi: [15, 25, 35, 45, 55, 50, 40, 30, 20, 10]

Verilən sıra 15-dən 55-ə qədər artır və sonra 10-a enir,

Çıxış: 55

b) Giriş massivi: [1, 3, 9, 8, 6, 4, 2]

Verilən sıra 1-dən 9-ə qədər artır və sonra 2-a enir,

Çıxış: 9

Yanaşma 1

Alqoritm

  1. Maksimum başlanğıc = INT_MIN.
  2. Dizidə keçin və maksimum <array [i] maksimumunu yeniləyinsə, bütün elementləri maksimumla müqayisə edin.
  3. Dizini tamamilə keçdikdən sonra maksimum yazdırın.

Həyata keçirilməsi

Bir massivdə maksimum element üçün C ++ proqramı

#include <bits/stdc++.h> 
#include <limits.h> 
using namespace std; 
/*Main function*/ 
int main() 
{ 
    int input_array[] = {15,25,35,45,55,50,40,30,20,10}; 
    int N = sizeof(input_array)/sizeof(input_array[0]); 
    int max = INT_MIN; 
    for(int i = 0; i <= N-1; i++) 
    { 
        if(input_array[i] > max) 
        { 
            max = input_array[i]; 
        } 
    } 
    cout<<"Maximum element:"<<max; 
    return 0;
}
Maximum element:55

Bir massivdə maksimum element üçün Java Proqramı

import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int max = -1; 
        for(int i = 0; i <= n-1; i++) 
        { 
            if(a[i]>max) 
            { 
                max = a[i]; 
            } 
        } 
        System.out.println("Maximum element:"+max); 
        }
}
5
1 3 5 2 1
5

Bir sıra içindəki maksimum element üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (n) burada n - massivdə mövcud olan elementlərin sayı. Burada bütün elementləri təkrarlayırıq və növbəti elementin əvvəlki elementdən daha böyük olduğu vəziyyəti yoxlayırıq. Bu vəziyyət vurduqdan sonra cavabımızı yazdırırıq və döngəni pozuruq.

Kosmik Mürəkkəblik

O (1) çünki burada çox köməkçi yerdən istifadə etmirik.

Yanaşma 2

Alqoritm

Burada dəyişdirilmiş istifadə edirik İkili axtarış.

  1. Orta elementi əvvəlki və sonrakı elementlərlə müqayisə edirik, orta əvvəlki və sonrakıdan böyükdürsə, orta maksimumdur, maksimum qayıdın.
  2. Orta növbəti elementdən böyük və əvvəlki elementdən kiçikdirsə, maksimum ortanın sol hissəsində olacaq. Beləliklə, sol hissədə axtarın.
  3. Orta, sonrakıdan az və əvvəlki elementdən böyükdürsə, maksimum ortanın sağ hissəsində olacaq. Beləliklə, sağ hissədə axtarın.

Həyata keçirilməsi

Bir massivdə maksimum element üçün C ++ proqramı

#include <bits/stdc++.h>
#include <limits.h>
using namespace std;
int FindMax(int array[], int low, int high)
{
   if(low == high)//only one element
   {
     return array[low];
   }
   if((high- 1 == low))//if two elements present, return maximum element
   {
      if(array[low] >= array[high])
      {
        return array[low];
      }
      else
      {
        return array[high];
      }
   }     
   int mid = (low + high)/2;
   //If mid is greater than previous and next, mid is maximum so, return maximum
   if(array[mid]>array[mid+1] && array[mid]>array[mid-1])
   {
      return array[mid];
   }
   //If mid is greater than its next element and smaller than its previous element
   //then maximum will be in left part of the mid
   if(array[mid]>array[mid+1] && array[mid]<array[mid-1])
   {
     return FindMax(array,low,mid-1);
   }
   //If mid is less than its next and greater than previous element
   //then maximum will be in right part of mid
   else
   {
     return FindMax(array,mid+1,high);
   }
}
 
/*Main function to print maximimum*/
int main()
{
   int input_array[] = {15,25,35,45,55,50,40,30,20,10};
   int N = sizeof(input_array)/sizeof(input_array[0]);
   cout<<"Maximum element:"<<FindMax(input_array,0,N-1);
   return 0;
}
Maximum element:55

Bir massivdə maksimum element üçün Java Proqramı

import java.util.Scanner;
class sum
{
    public static int FindMax(int array[], int low, int high)
    {
       if(low == high)//only one element
       {
         return array[low];
       }
       if((high- 1 == low))//if two elements present, return maximum element
       {
          if(array[low] >= array[high])
          {
            return array[low];
          }
          else
          {
            return array[high];
          }
       }     
       int mid = (low + high)/2;
       //If mid is greater than previous and next, mid is maximum so, return maximum
       if(array[mid]>array[mid+1] && array[mid]>array[mid-1])
       {
          return array[mid];
       }
       //If mid is greater than its next element and smaller than its previous element
       //then maximum will be in left part of the mid
       if(array[mid]>array[mid+1] && array[mid]<array[mid-1])
       {
         return FindMax(array,low,mid-1);
       }
       //If mid is less than its next and greater than previous element
       //then maximum will be in right part of mid
       else
       {
         return FindMax(array,mid+1,high);
       }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        System.out.println("Maximum element:"+FindMax(a,0,n-1)); 
    }
}
7
6 4 3 2 98 3 1
98

Bir sıra içindəki maksimum element üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (logn) burada n - massivdə mövcud olan elementlərin sayı. Burada ikili axtarışdan istifadə edirik alqoritm dəyişdirilmiş bir şəkildə.

Kosmik Mürəkkəblik

O (1) çünki burada çox köməkçi yerdən istifadə etmirik.

References

Translate »