Ο μικρότερος θετικός αριθμός λείπει σε μια σειρά χωρίς ταξινόμηση


Επίπεδο δυσκολίας Σκληρά
Συχνές ερωτήσεις Απολύτως πλίθα αμαζόνα μήλο Bloomberg ByteDance Βάσεις δεδομένων eBay Facebook Γεγονότα Goldman Sachs Google JP Morgan Microsoft Morgan Stanley μαντείο Salesforce Samsung Snapdeal Tencent Τέσλα Twitch Uber Εργαστήρια Walmart Επιθυμώ
Παράταξη Booking.com

Δήλωση προβλήματος

Στο δεδομένο χωρίς ταξινόμηση παράταξη βρείτε τον μικρότερο θετικό αριθμό που λείπει σε έναν μη ταξινομημένο πίνακα. Ένας θετικός ακέραιος αριθμός δεν περιλαμβάνει 0. Μπορούμε να τροποποιήσουμε τον αρχικό πίνακα αν χρειαστεί. Ο πίνακας μπορεί να περιέχει θετικούς και αρνητικούς αριθμούς.

Παράδειγμα

a. Πίνακας εισόδου: [3, 4, -1, 0, -2, 2, 1, 7, -8]

Έξοδος: 5.
Στην δεδομένη συστοιχία υπάρχουν 1,2,3,4 αλλά 5 απουσιάζει, ο οποίος είναι ο μικρότερος θετικός αριθμός που λείπει στον δεδομένο πίνακα.

b. Πίνακας εισόδου: [2, 3, 7, 8, -1, -2, 0]

Έξοδος: 1.
Στην δεδομένη συστοιχία 1 απουσιάζει, που είναι ο μικρότερος θετικός αριθμός που λείπει στον δεδομένο πίνακα.

c. Πίνακας εισόδου: [2, 3, 7, 8, -1, -2, 0]

Έξοδος: 1.
Στην δεδομένη συστοιχία 1 απουσιάζει, που είναι ο μικρότερος θετικός αριθμός που λείπει στον δεδομένο πίνακα.

Ο αλγόριθμος για τον μικρότερο θετικό αριθμό λείπει σε μια σειρά χωρίς ταξινόμηση

1. Πρέπει να βρούμε τον μικρότερο θετικό αριθμό που λείπει, επομένως δεν χρειαζόμαστε αρνητικούς αριθμούς. Έτσι, δημιουργούμε μια συνάρτηση για τη μετακίνηση όλων των θετικών αριθμών στο τέλος του πίνακα και βρίσκουμε τους αριθμούς που λείπουν στο θετικό πίνακα.

2. Στη λειτουργία positive_array,

  • Διασχίζουμε τον πίνακα με δύο δείκτες, αν βρούμε έναν αρνητικό αριθμό, το ανταλλάξουμε με τον δείκτη έναρξης και τον προωθούμε.
  • Συνεχίζουμε αυτό μέχρι να φτάσει στο τέλος του πίνακα και επιστρέφουμε τον δείκτη έναρξης του θετικού πίνακα. Ποια είναι η θέση δείκτη εκκίνησης, όταν φτάσουμε στο τέλος του πίνακα.

3. Δημιουργούμε μια λειτουργία FindMissingPostive που λαμβάνει τον πίνακα και το μέγεθος του πίνακα και δίνει τον μικρότερο αριθμό που λείπει.

4. Σε αυτή τη λειτουργία,

  • ένα. Στον πίνακα εισαγωγής, αν βρούμε έναν θετικό ακέραιο, επισημαίνουμε ότι επισκέφθηκε την τιμή μου στη θέση του ευρετηρίου σε αρνητική. Παράδειγμα: Εάν ο δεδομένος πίνακας είναι πίνακας []. Σε αυτόν τον πίνακα, αν βρούμε 2, κάνουμε τον πίνακα [1] = -2 και ούτω καθεξής μέχρι το τέλος του πίνακα μόνο εάν ο πίνακας [i] - 1 <size και array [array [i] - 1]> 0.
  • Μετά την τροποποίηση του πίνακα. Εάν ο δείκτης στον οποίο βρίσκουμε τον πρώτο θετικό αριθμό είναι k. Στη συνέχεια, το k + 1 είναι ο μικρότερος αριθμός που λείπει. Εάν δεν βρήκαμε θετικό αριθμό τότε, το μέγεθος του πίνακα + 1 είναι ο μικρότερος αριθμός που λείπει.

5. Για τον δεδομένο πίνακα εισαγωγής, εφαρμόζουμε πρώτα το positive_arrayfunction (αφήστε το να επιστρέψει j) και εφαρμόζουμε το FindMissingPostive on (array + j).

Εκτέλεση

Το πρόγραμμα C ++ για τον μικρότερο θετικό αριθμό λείπει σε μια σειρά χωρίς ταξινόμηση

#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;
}

Πρόγραμμα Java για τον μικρότερο θετικό αριθμό λείπει σε μια σειρά χωρίς ταξινόμηση

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

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

O (n) όπου n είναι το μέγεθος του δεδομένου πίνακα. Εδώ διασχίζουμε τον πίνακα μόνο μία φορά και έχουμε τον μικρότερο θετικό αριθμό που λείπει.

Διαστημική πολυπλοκότητα

Ο (1) γιατί εδώ χρησιμοποιούμε μερικές μεταβλητές για να υπολογίσουμε την απάντηση.

αναφορές