Берилген массивдин кандайдыр бир ички жыйындысынын суммасы катары чагылдырууга болбогон эң кичинекей оң бүтүн маанини табыңыз  


Кыйынчылык деңгээли жеңил
Көп суралган Databricks Fab Taxi4Sure UHG Optum
согуштук тизме

Маселени билдирүү  

Сизге а сорттолгон бүтүн сандар массиви. Берилгендин кандайдыр бир ички жыйындысынын суммасы катары чагылдырылбаган эң кичинекей оң бүтүн санды табышыбыз керек согуштук тизме.

мисал  

arr[] = {1,4,7,8,10}
2

Түшүндүрмө: 2ди сумма катары көрсөтө турган бир дагы суб-массив жок.

arr[] = {1,2,3,5,7,9}
28

Түшүндүрмө: 28ди сумма катары көрсөтө турган бир дагы суб-массив жок.

 

Берилген массивдин кандайдыр бир ички жыйындысынын суммасы катары чагылдырылбаган эң кичине оң бүтүн санды табуу алгоритми  

1. Set output to 1.
2. From i=0 to i less than n.
  1. Check if arr[i] is less than equal to output.
    1. Update the value of output to the sum of output and arr[i].
3. Return output.

 

түшүндүрүү

Берилген массивдин кандайдыр бир ички жыйындысынын суммасы катары чагылдырууга болбогон эң кичинекей оң бүтүн маанини табыңызтөөнөч

 

 

Бизге бүтүн сандардын иреттелген массиви берилет. Маселенин коюлушу эң кичине оң бүтүн маанини табууну суранат. Муну берилген массивдин кандайдыр бир топтомунун суммасы катары чагылдыруу мүмкүн эмес. Бул чечимди сызыктуу түрдө таба алабыз убакыттын татаалдыгы O (n). Бизде буга чейин эле иреттелген массив бар. Ошентип, тартип же сан айырмачылыгы жөнүндө кабатыр болбошубуз керек, ошондуктан биз муну сызыктуу убакытта таба алабыз.

ошондой эле
Кыстаруу ордун издөө

Биз массивди аралайбыз. Бирок ага чейин чыгарылган нерсенин маанисин 1 деп койсоңуз, жок дегенде эң кичине оң бүтүн сан болот. Эгерде бизде 1ден башталбаган массив жок болсо, анда ал жөн гана 1ди чыгуучу маани катары кайтарып берет. Ошентип, чыгымдын маанисин 1 кылып орноткондон кийин, массивди аралап өтүңүз. Биз массивдин биринчи элементин алып, анын чыгарылган нерсенин маанисинен кичине же барабар экендигин текшеребиз. Эгер бул чын болсо, анда биз чыгымдын жана учурдагы массив элементинин маанисин кошобуз. Анан аны чыгаруу үчүн сактаңыз. Массив элементинин мааниси натыйжанын маанисинен ашпаганга чейин, биз муну жасай беребиз. Ошондо ал циклден чыгат жана биз чыгарылган наркты кайтарып беребиз.

Эгер arr [] = {1,4,7,8,10} деп мисал алсак, анда натыйжасы = 1 менен баштайбыз, биринчи элементин тандап алууну улантабыз жана анын чыгарылышына аз же барабар экендигин текшеребиз , бул чын жана биз чыгымдын жана arr [i] маанисин кошуп, аны чыгарууга сактайбыз жана бизде азыр 2 бар. Кайра биз баалуулуктарды текшерип көрөбүз, бирок эми массивдеги каалаган маани чыкканга барабар же аз эмес, ошондуктан акыры 2 биздин жоопубуз жана аны кайтарып беребиз.

Берилген массивдин кандайдыр бир ички жыйындысынын суммасы катары чагылдырылбаган эң кичинекей оң бүтүн санды табуу үчүн код  

C ++ коду

#include<iostream>

using namespace std;

int getSmallestInteger(int arr[], int n)
{
    int output = 1;
    for (int i = 0; i < n && arr[i] <= output; i++)
        output = output + arr[i];

    return output;
}
int main()
{
    int arr[] = {1, 3, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout <<"Smallest positive integer : "<<getSmallestInteger(arr, n);

    return 0;
}
Smallest positive integer : 2

 

ошондой эле
Массив Leetcode чечиминдеги эки элементтин максималдуу продуктусу

Java Code

class IntegernotSumofSubArray
{
    public static int getSmallestInteger (int arr[], int n)
    {
        int output = 1;

        for (int i = 0; i < n && arr[i] <= output; i++)
            output = output + arr[i];

        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {1, 3, 4, 5};
        int n = arr.length;
        System.out.println("Smallest positive integer : "+getSmallestInteger (arr, n));
    }
}
Smallest positive integer : 2

 

Комплекстик анализ  

Массивдин ички суммасы катарында жок болгон эң кичинекей оң сандын маанисин табууга убакыттын татаалдыгы

Качан гана биз массивден өтсөк, биз убакыттын сызыктуу татаалдыгын жасайбыз. Бул жерде биз бир гана өтүүдөн башка эч нерсе жасабай жаткандыктан, бизде сызыктуу убакыт татаалдыгы бар. O (N) кайда "N"  массивдеги элементтердин саны.

Массивде подсумка суммасы катары жок болгон эң кичинекей оң сандын маанисин табуу үчүн мейкиндиктин татаалдыгы

Бизде жөн гана киргизилген бир массив бар, ошондуктан алгоритм мейкиндиктин сызыктуу татаалдыгына ээ. O (N) кайда "N"  массивдеги элементтердин саны.