Нөл сомасы бар барлық үшемдерді табыңыз  


Күрделілік дәрежесі орта
Жиі кіреді Amazon GE Healthcare Google жорық
Array Hash іздеу Сұрыптау

«Нөлдік қосындысы бар барлық үштіктерді табу» мәселесінде сізге оң және теріс сандардан тұратын жиым берілгені айтылған. Есептер қосындысы 0-ге тең үштікті табуды сұрайды.

Нөл сомасы бар барлық үшемдерді табыңыз

мысал  

arr[] = {0,-2,1,3,2,-1}
(-2 -1  3) (-2 0  2) (-1 0  1)

Түсіндіру

Бұл қосындысы 0 болатын үшемдер.

(-2 + -1 + 3 = 0) (-2 + 0 + 2 = 0) (-1+ 0 + 1 = 0)

arr[] = {2,4,-5,-1,3}
(-5 2 3)

Түсіндіру

Сандардың қосындысы 0 ⇒ -5 + 2 + 3 = 0 болатын үштіктер

Алгоритм  

  1. сорт берілген жиым.
  2. Орнатыңыз Бульдік айнымалы табылды жалған
  3. I = 0-ден i-ге дейін цикл
    1. жиынтық fir = i + 1, sec = n-1 және басқа айнымалы x массивтің ағымдағы элементіне.
    2. Шырша кезінде
      1. Элементтердің үшеуі бірге 0-дің қосындысын құрайтынын тексеріңіз.
        1. Егер шын болса, онда барлық үш санды басып шығарыңыз және «Ақиқат» мәнін орнатыңыз.
      2. Үш элементтің (ағымдағы массив элементтері) қосындысы 0-ден аз екенін тексеріңіз.
        1. Егер рас болса, онда шыршаның мәнін 1-ге арттырыңыз.
      3. Үш элементтің қосындысы 0-ден үлкен екенін тексеріңіз.
          1. Егер рас болса, онда сек мәнін 1-ге азайтыңыз.
  4. IsFound жалған болып қалатындығын тексеріңіз, яғни үштік түзілмейді.

Түсіндіру

Бізге массив берілген. Содан кейін біз қосындысы 0-ге тең массивте берілген сандармен жасалуы мүмкін үштіктерді анықтауды сұраймыз. Біз кірістірілген циклды қолданамыз. Бұл алгоритм тұрақты кеңістікте жұмыс істей алады. Біріншіден, біз массивті сұрыптайтын боламыз. Осылайша біз екі көрсеткішті техниканы қолдана аламыз. Біз бір логикалық айнымалы деп жариялаймыз және оның мәнін алдымен false деп қоямыз. Бұл мәні 0-ге тең элементтері бар үштіктердің ешқайсысын таппауды қамтамасыз ету үшін қажет табылды жалған болып қалады. Содан кейін біз үштікті тапқан сайын оны шындыққа айналдырамыз. Сонымен, біз үштік табылмады деген қорытынды жасауға болады.

Сондай-ақ, қараңыз
Жою және табу

Алдымен массивті кірістірілген циклда сұрыптаймыз. Содан кейін біз n-1 массиві бойынша өтеміз. Бастапқы мәнді i + 1, соңғы мәнді n-1, ал х - сыртқы циклдегі ағымдағы мәнге қоямыз. Ішкі циклде біз массивтің мәндерін айналып өтіп, барлық үш элементтің (x + arr [fir] + arr [sec]) қосындысының 0-ге тең екендігін немесе болмауын тексереміз. Егер ол 0-ге тең болса, онда біз бірінші жұпты таптық және жиымның барлық ағымдағы мәндерін шығарамыз және isFound мәнін true мәніне орнатамыз.

Бұл біз жұптардың бірін тапқанымызды көрсетеді. Егер үштік қосындысы 0-ге тең болмаса, біз үш ағымдағы элементтің қосындысы 0-ден аз екенін тексереміз. Егер қосынды 0-ден аз болса, онда біз шамды өсіреміз, бұл біздің бастапқы мәніміз жоғарылағанын білдіреді. Егер шарт қанағаттандырылмаса. Қосындының 0-ден үлкен екендігін тексереміз, егер рас болса, сек.

Осылайша, біз 0-ге тең болуы мүмкін барлық үштіктерді табамыз.

Нөл сомасы бар барлық үштіктерді табуға арналған C ++ коды  

#include<iostream>
#include<algorithm>

using namespace std;

void getTripletZero(int arr[], int n)
{
    bool isFound = false;
    sort(arr, arr+n);

    for (int i=0; i<n-1; i++)
    {
        int fir = i + 1;
        int sec = n - 1;
        int x = arr[i];
        while (fir < sec)
        {
            if (x + arr[fir] + arr[sec] == 0)
            {
                cout<<"("<<x<<" "<<arr[fir]<<" "<< arr[sec]<<")"<<endl;
                fir++;
                sec--;
                isFound = true;
            }
            else if (x + arr[fir] + arr[sec] < 0)
                fir++;
            else
                sec--;
        }
    }
    if (isFound == false)
        cout << " There is no triplet can be formed..!" << endl;
}
int main()
{
    int arr[] = {0,-2,1,3,2,-1};
    int n = sizeof(arr)/sizeof(arr[0]);
    getTripletZero(arr, n);
    return 0;
}
(-2 -1 3)
(-2 0 2)
(-1 0 1)

Нөл сомасы бар барлық үштіктерді табуға арналған Java коды  

import java.util.Arrays;

class TripletSumzero
{
    public static void getTripletZero(int arr[], int n)
    {
        boolean isFound = false;

        Arrays.sort(arr);

        for (int i=0; i<n-1; i++)
        {
            int fir = i + 1;
            int sec = n - 1;
            int x = arr[i];
            while (fir < sec)
            {
                if (x + arr[fir] + arr[sec] == 0)
                {
                    System.out.println("(" + x + " "+arr[fir]+ " "+" "+arr[sec]+")");
                    fir++;
                    sec--;
                    isFound = true;
                }
                else if (x + arr[fir] + arr[sec] < 0)
                    fir++;
                else
                    sec--;
            }
        }
        if (isFound == false)
            System.out.println(" There is no triplet can be formed..!");
    }
    public static void main (String[] args)
    {
        int arr[] = {0,-2,1,3,2,-1};
        int n =arr.length;
        getTripletZero(arr, n);
    }
}
(-2 -1  3)
(-2 0  2)
(-1 0  1)

Күрделілікті талдау  

Уақыттың күрделілігі

O (n2) қайда «N»  - бұл массивтегі элементтер саны. Біз O (n) уақытына үлес қосатын екі көрсеткіш техникасын қолданамыз. Бірақ техниканың өзі O (n) уақыт ішінде қолданылады. Сонымен, алгоритмді O (n ^ 2) уақытында орындау керек.

Сондай-ақ, қараңыз
3 сома

Ғарыштың күрделілігі

O (1) өйткені қосымша орын қажет емес.