لږترلږه ترتیب شوي صف کې لږترلږه ومومئ


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي ایڈوب ترلاسه کړئ Amazon د Microsoft Morgan سټنلي سامسنګ سنیپډیل ټایمز انټرنیټ
پیشه دوه لمبري پلټنه تقسیم او فتح لټون کول

ستونزه بیان

"لږترلږه ترتیب شوي صف کې لږترلږه ومومئ" په ګوته کوي چې تاسو ته د اندازې ترتیب شوی سرنی درکول کیږي کوم چې په ځینې شاخص کې څرخیږي. لږترلږه عنصر په سور.

بېلګه

لږترلږه ترتیب شوي صف کې لږترلږه ومومئ

a[ ] = {5, 1, 2, 3, 4}
1

توضیحي: که چیرې موږ په ترتیب شوي ترتیب کې ارਾਰੇ تنظیم کړو نو دا به [1 ، 2 ، 3 ، 4 ، 5] وي. نو له دې ټولو څخه خورا کوچنۍ شمیره 1 ده. او له همدې امله محصول 1 دی.

a[ ] = {5, 2, 3, 4}
2

خطي لټون

الګوریتم

1. Initialize a sorted rotated array a[ ] of size n.
2. Create a function to find the minimum in a rotated sorted array which accepts an integer variable as it's a parameter.
3. Initialize an integer variable min as the first element in the given array.
4. Traverse through the given array and check if the element at current index in array a[ ] is less than variable min, update min as current element.
5. Return the integer variable min.

موږ کولی شو خطي لټون وکاروو یا په ساده ډول د ننوت صف یو ځل وګرځوو او په یو ټریول کې کوچنی عنصر ومومو. موږ به په ساده ډول په صف کې د ټولو عناصرو څخه لوپ کړو او که موږ داسې شمیره ومومئ چې زموږ له لږترلږه څخه لږ وي ، نو موږ خپل ځواب تازه کوو.

کوډ

C ++ برنامه د ټاکل شوي ترتیب شوي ترتیب کې لږترلږه موندلو لپاره

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

int findMin(int a[], int n){
    int min = a[0];
    for(int i=1; i<n; i++){
        if(a[i]<min){
            min = a[i];
        }
    }
    return min;
}

int main() {
  int a[] = {5, 2, 3, 4};
  int n = sizeof(a)/sizeof(a[0]);
  cout<<findMin(a, n);
  return 0;
}
2

د جاوا پروګرام د ټاکل شوي ټاکل شوي ترتیب کې لږترلږه موندلو لپاره

class MinSearch{
    
    static int findMin(int a[], int n){
        int min = a[0];
        for(int i=1; i<n; i++){
            if(a[i]<min){
                min = a[i];
            }
        }
        return min;
    }
    
  public static void main (String[] args){
    int a[] = {5, 2, 3, 4};
      int n = a.length;
      System.out.println(findMin(a, n));
  }
}


2

د پیچلتیا تحلیل

د وخت پیچلتیا

O (N) ،  ځکه چې موږ په صف کې د ټولو عناصرو څخه تعقیب شو ، کوم چې موږ ته اجازه راکوي د خطي وخت پیچلتیا لاسته راوړو.

د ځای پیچلتیا

O (1) ، الګوریتم پخپله مستقل ځای نیسي مګر برنامه په بشپړ ډول خطي ځای نیسي ځکه چې د آخذې صفاتو ساتلو له امله.

دوه لمبري پلټنه

الګوریتم

1. Initialize a sorted rotated array a[ ] of size n.
2. Create a function to find the minimum in a rotated sorted array which accepts an integer variable as it's a parameter.
3. Initialise the three variables beg = 0, end = n-1 and mid = beg+(end-beg)/2.
4. Check if the variable end is less than the variable beg, return a[0].
5. If the variable end is equal to the variable beg, return a[beg].
6. If the variable mid is less than the variable end and a[mid+1] is less than a[mid], return a[mid+1].
7. If mid is greater than beg and a[mid] is less than a[mid+1], return a[mid].
8. If a[end] is greater than a[mid], make a recursive call to function with parameters a, beg, mid-1.
9. Return the recursive call to function itself with the parameters a, mid+1, and end.

خورا مؤثره لاره به د بائنری لټون کارولو لپاره وي ځکه چې ننوت صف یو ټاکل شوی ترتیب شوی صف دی. دا صف دی ترتیب شوی مګر دا په یو ټکی کې وګرځید. له هغه وخته چې د بائنری لټون لوګارتمیک وخت پیچلتیا اخلي. دا غوره ده چې د پورتنۍ یوې په پرتله دا حل وکاروئ.

د بائنري لټون په کارولو سره په ټاکل شوي ترتیب شوي قطار کې لږترلږه موندلو لپاره کوډ

C ++ برنامه

#include <bits/stdc++.h> 
using namespace std; 
  
int findMin(int a[], int beg, int end){  
    if(end < beg) 
        return a[0];  
  
    if(end==beg) 
        return a[beg];  
  
    int mid = beg + (end - beg)/2; 
  
    if(mid<end && a[mid + 1]<a[mid])  
        return a[mid + 1];  
  
    if(mid>beg && a[mid]<a[mid - 1])  
        return a[mid];  
  
    if(a[end]>a[mid])  
    return findMin(a, beg, mid - 1);  
    return findMin(a, mid + 1, end);  
}  
  
int main(){  
    int a[] = {5, 2, 3, 4}; 
    int n = sizeof(a)/sizeof(a[0]);  
    cout<<findMin(a, 0, n-1);  
    return 0;  
}
2

جاوا پروګرام

class MinSearch{ 
   
    static int findMin(int a[], int beg, int end){ 
        
        if(end < beg) 
            return a[0]; 
            
        if(end==beg) 
            return a[beg];
            
        int mid = beg + (end - beg)/2; 
        
        if(mid<end && a[mid + 1]<a[mid]) 
            return a[mid + 1]; 
        
        if(mid>beg && a[mid]<a[mid - 1]) 
            return a[mid]; 
        
        if(a[end]>a[mid]) 
            return findMin(a, beg, mid - 1); 
        return findMin(a, mid + 1, end); 
    }
        
    public static void main (String[] args){ 
        int a[] = {5, 2, 3, 4}; 
        int n = a.length; 
        System.out.println(findMin(a, 0, n-1)); 
    } 
}
2

د پیچلتیا تحلیل

د وخت پیچلتیا

او (نګ ن) چیرې چې N د ننوت په صف کې د عناصرو شمیر دی. دلته موږ بائنري لټون کارولی چې د لوګارتمیک وخت پیچلتیا اخلي. دا ټول ممکنه دي ځکه چې سرنی په پیل کې ترتیب شوی و.

د ځای پیچلتیا

O (1) ، دا لید هم مستقل وخت نیسي مګر برنامه په بشپړ ډول د O (N) ځای نیسي ځکه چې د داخلي ځای ساتلو لپاره اړین ځای دی.