未排序數組中丟失的最小正數  


難度級別
經常問 ol石 土磚 亞馬遜 蘋果 彭博社 ByteDance 數據塊 易趣 Facebook 事實集 高盛 谷歌 JP摩根 Microsoft微軟 摩根士丹利(Morgan Stanley) 神諭 Salesforce的 Samsung Snapdeal 騰訊 特斯拉 Twitch 尤伯杯 沃爾瑪實驗室 希望
排列 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. 在此功能中,

  • 一種。 在輸入數組中,如果找到一個正整數,則將其標記為我訪問過的值,使索引位置的值變為負數。 示例:如果給定的數組是array []。 在此數組中,如果找到2,則只有在array [i] – 1 <size和array [array [array [i] – 2]> 1]的情況下,使array [1] = -0依此類推,直到數組末尾。
  • 修改數組後。 如果找到第一個正數的索引是k。 那麼,k + 1是最小的遺漏數。 如果找不到正數,則數組的大小+ 1是最小的缺失數。

5. 對於給定的輸入數組,我們首先應用positive_arrayfunction(讓它返回j),然後將FindMissingPostive應用於(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是給定數組的大小。 在這裡,我們只遍歷數組一次,得到最小的正缺失數。

也可以看看
重複子陣列的最大長度

空間複雜度

O(1) 因為這裡我們使用一些變量來計算答案。

參考