Çeşidlənməmiş Dizidəki Ən Kiçik Müsbət Sayı

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Akkolit Çiy kərpic Amazon alma Bloomberg ByteDance Verilənlər bazası eBay Facebook Məlumat dəsti Goldman Sachs google JP Morgan microsoft Morgan Stanley Kahin Salesforce Samsung Snapdeal Tencent Tesla Twitch Über Walmart Laboratoriyaları Arzu
Geyim Booking.comBaxılıb 1119

Problem bəyanat

Verilmiş çeşidlənməmişdir array çeşidlənməmiş massivdə itkin olan ən kiçik müsbət ədədi tapın. Müsbət tam ədədə 0 daxil deyil. Lazım gələrsə orijinal massivi dəyişə bilərik. Dizidə müsbət və mənfi rəqəmlər ola bilər.

misal

a. Giriş massivi: [3, 4, -1, 0, -2, 2, 1, 7, -8]

Çıxış: 5.
Verilən massivdə 1,2,3,4 mövcuddur, lakin 5 yoxdur, bu, verilmiş massivdə itkin olan ən kiçik müsbət rəqəmdir.

b. Giriş massivi: [2, 3, 7, 8, -1, -2, 0]

Çıxış: 1.
Verilən massivdə 1 yoxdur, bu verilən massivdə itkin olan ən kiçik müsbət rəqəmdir.

c. Giriş massivi: [2, 3, 7, 8, -1, -2, 0]

Çıxış: 1.
Verilən massivdə 1 yoxdur, bu verilən massivdə itkin olan ən kiçik müsbət rəqəmdir.

Çeşidlənməmiş bir sıra içərisində itkin düşən ən kiçik müsbət ədədin alqoritmi

1. Ən kiçik itkin müsbət ədədi tapmalıyıq, buna görə mənfi rəqəmlərə ehtiyacımız yoxdur. Beləliklə, bütün müsbət rəqəmləri massivin sonuna daşımaq üçün bir funksiya yaradırıq və itkin rəqəmləri müsbət massivdə tapırıq.

2. Pozitiv_array funksiyasında,

  • Dizini iki göstərici ilə keçirik, mənfi bir rəqəm tapsaq, başlanğıc göstəricisi ilə dəyişdiririk və irəli aparırıq.
  • Bunu serialın sonuna çatana qədər davam etdiririk və pozitiv massivin başlanğıc indeksini qaytarırıq. Dizinin sonuna çatdığımızda başlanğıc göstəricisi mövqeyi.

3. Massivi və massivin ölçüsünü götürən və ən kiçik itkin nömrəni verən FindMissingPostive funksiyası yaradırıq.

4. Bu funksiyada

  • a. Giriş massivində müsbət tam ədədi tapsaq, indeks mövqeyindəki dəyəri mənfi hala gətirdiyimi qeyd etdim. Nümunə: Əgər verilən sıra massivdirsə []. Bu massivdə 2 tapsaq [1] = -2 massivini və s. Sona qədər yalnız sıra [i] - 1 <ölçüsü və massiv [array [i] - 1]> 0 olduqda düzəldirik.
  • Dizini dəyişdirdikdən sonra. İlk müsbət ədədi tapdığımız indeks k olarsa. O zaman k + 1 itkin olan ən kiçik rəqəmdir. Əgər müsbət bir rəqəm tapmasaq, +1 massivinin ölçüsü ən kiçik itkin saydır.

5. Verilən giriş massivi üçün əvvəlcə pozitiv_arrayfunksiyanı tətbiq edirik (qayıtsın j) və FindMissingPostive-ı (array + j) tətbiq edirik.

Həyata keçirilməsi

Sıralanmamış bir sıra içərisində itkin olan ən kiçik müsbət rəqəm üçün C ++ proqramı

#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>
using namespace std;
 
//function to swap addresses
void swap(int *a, int *b)
{
    int temp = *a;
    *a   = *b;
    *b   = temp;
}
//In this function we move non-postive elements to the start of the array
//return the start index of start index of postive array
int positive_array(int array[], int N)
{
    int start_index = 0, i;
    for(i = 0; i < N; i++)
    {
       if (array[i] <= 0)  
       {
           swap(&array[i], &array[start_index]);
           start_index++;  // increment count of non-positive integers
       }
    }
    return start_index;
}
//In the given array this function finds the smallest missing number
//N is size of the array
//we mark the elements by making the elements at the postion(i-1)to negitive
//after modifying the array we find index at which we find first postive(j) and j+1 is the missing number.
int FindMissingPostive(int array[], int N)
{
  for(int i = 0; i < N; i++)
  {
    if(abs(array[i]) < N+1 && array[abs(array[i]) - 1] > 0)
    {
      array[abs(array[i]) - 1] = -array[abs(array[i]) - 1];
    }
  }
  for(int k = 0; k < N; k++){
    if (array[k] > 0)
    {
      return k+1;
    }
  }
  return N+1;
}
//insted of finding the missing postive integer in whole array
//we can find in postive part of the array fast.
int FindMissing(int array[], int N)
{
   int start = positive_array(array,N);
 
   return FindMissingPostive(array+start,N-start);
}
//main function to test above functions 
int main()
{
  int N;//size of the array
  cin>>N;
  int a[N];
  for(int i=0;i<N;i++)
  {
      cin>>a[i];
  }
  cout<<"smallest positive number missing: = "<<FindMissing(a,N);
  return 0;
}

Çeşidlənməmiş bir sıra içərisində itkin düşən ən kiçik müsbət rəqəm üçün Java proqramı

import java.util.Scanner;

class sum
{
    public static int abs(int x)
    {
        if(x<0)
        {
            return -1*x;
        }
        else
        {
            return x;
        }
    }
    //In this function we move non-postive elements to the start of the array
    //return the start index of start index of postive array
    public static int positive_array(int array[], int N)
    {
        int start_index = 0, i;
        for(i = 0; i < N; i++)
        {
           if (array[i] <= 0)  
           {
               swap(array[i], array[start_index]);
               start_index++;  // increment count of non-positive integers
           }
        }
        return start_index;
    }
    //In the given array this function finds the smallest missing number
    //N is size of the array
    //we mark the elements by making the elements at the postion(i-1)to negitive
    //after modifying the array we find index at which we find first postive(j) and j+1 is the missing number.
    public static int FindMissingPostive(int array[], int N)
    {
      for(int i = 0; i < N; i++)
      {
        if(abs(array[i]) < N+1 && array[abs(array[i]) - 1] > 0)
        {
          array[abs(array[i]) - 1] = -array[abs(array[i]) - 1];
        }
      }
      for(int k = 0; k < N; k++){
        if (array[k] > 0)
        {
          return k+1;
        }
      }
      return N+1;
    }
    //insted of finding the missing postive integer in whole array
    //we can find in postive part of the array fast.
    public static int FindMissing(int array[], int N)
    {
       int start = 0;
        for(int i = 0; i < N; i++)
        {
           if (array[i] <= 0)  
           {
               array[i]=array[i]+array[start]-(array[start]=array[i]);
               start++;  // increment count of non-positive integers
           }
        }
       int temp[] = new int[N-start];
       for(int i=0;i<N-start;i++)
       {
           temp[i]=array[i+start];
       }
       return FindMissingPostive(temp,N-start);
    }
    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("smallest positive number missing: = "+FindMissing(a,n));
    }
}
9
3 4 -1 0 -2 2 1 7 -8
smallest positive number missing: = 5

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n) burada n verilən massivin ölçüsüdür. Burada serialı yalnız bir dəfə keçirik və ən kiçik müsbət itkin rəqəmi alırıq.

Kosmik Mürəkkəblik

O (1) çünki burada cavabı hesablamaq üçün bəzi dəyişənlərdən istifadə edirik.

References

Translate »