Айқын элементтері бар ішкі массивтер


Күрделілік дәрежесі орта
Жиі кіреді Cisco FreeCharge Times Internet Зохо
Array Hash Хэш

Проблемалық мәлімдеме

«Айқын элементтері бар ішкі массивтер» сізге бүтін элементтер жиыны берілгендігін айтады. Проблемалық есеп барлық элементтері бір-бірінен өзгеше болатын іргелес ішкі жиымдардың ұзындықтарының қосындысын табуды сұрайды.

мысал

arr[] = {3, 1, 2, 1}
4

Түсініктеме: ішкі жиымдар are (3, 1, 2), (3, 1), (1, 2), (2,1), (3), (1), (2), (1)

Барлық элементтердің жалпы ұзындығы (3 + 2 + 2 + 2 + 1 + 1 + 1 + 1) = 10.

Айқын элементтері бар ішкі массивтер

arr[] = {3, 5, 8, 9}
20

Түсініктеме: ішкі массивтер ⇒ (3), (5), (8), (9), (3, 5), (5, 8), (8, 9), (3, 5, 8), (5, 8, 9), (3, 5, 8, 9)

Барлық элементтердің жалпы ұзындығы (1 + 1 + 1 + 1 + 2 + 2 + 2 +3 +3 +4) = 10.

Айқын элементтері бар ішкі массивтерді табу алгоритмі

1. Declare a map.
2. Set output and j to 0.
3. Traverse the array from i=0 to i<n(length of an array).
  1. While j is less than n and if a set doesn’t contain the value of arr[j].
    1. Insert all the values of arr [j].
  2. Update the output to output +=((j - i) * (j - i + 1))/2.
  3. Remove the arr[i] from Set.
4. Return output.

Түсіндіру

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

Массивті айналып өтіп, а while цикл. J мәнін 0-ге және ішіне орнатыңыз while цикл біз j-ді ұлғайта отырып, циклдан өтеміз. Оған бірнеше шарт қойыңыз, ал j - n-ден аз, яғни массивтің ұзындығы, сонымен қатар Set [arr] мәнінің құрамында екендігі анықталған жағдайда. Мысалды қарастырайық:

Arr [] = {3, 1, 2, 1}

Біз әрбір элементті бір уақытта жинайтын массивті айналып өтеміз, бірінші рет 3 таңдаймыз делік, arr [j] -де, сыртқы циклды біраз уақыт тұрақты ұстап тұру керек, осы 3 басталады. while цикл, өйткені j 0 инициализацияланған, және жиынтықта алғаш рет 3 болмайды, сондықтан ол а-ға кіреді while цикл және [j] 3 мағынасын беріп, j ++ мәнін көбейтіңіз, келесі элементті 1 етіп таңдайды, жиынтық оны қамтымайды, сондықтан ол жиынтыққа енгізіледі, содан кейін 2 шығады, содан кейін 1 келеді, бірақ бұл жолы 1 циклде болғандықтан, ол шығады while цикл.

Енді біз циклден шыққан кезде j-тің мәні жоғарылайды, сондықтан шығуды соған сәйкес жаңартамыз. Әрі қарай өту үшін біз жиым элементін алып тастауымыз керек, осылайша ішкі жиымдағы бөлек элементтер қосындысының мүмкін болатын ұзындығын біле аламыз. Ақыр соңында, біз бұл өнімді қайтарамыз.

код

Айқын элементтері бар ішкі аралықтарды табу үшін C ++

#include<iostream>
#include<unordered_set>

using namespace std;

int getLength(int arr[], int n)
{
    unordered_set<int> SET;

    int j = 0, output = 0;
    for (int i=0; i<n; i++)
    {
        while (j < n && SET.find(arr[j]) == SET.end())
        {
            SET.insert(arr[j]);
            j++;
        }
        output += ((j - i) * (j - i + 1))/2;
        SET.erase(arr[i]);
    }
    return output;
}
int main()
{
    int arr[] = {3, 1, 2, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getLength(arr, n);
    return 0;
}
13

Айқын элементтері бар ішкі массивтерді табуға арналған Java коды

import java.util.Set;
import java.util.HashSet;

class LengthOfDistinctElements
{
    public static int getLength(int[] arr, int n)
    {
        Set<Integer> SET = new HashSet<>();
        int j = 0, output = 0;
        for (int i = 0; i < n; i++)
        {
            while (j < n && !SET.contains(arr[j]))
            {
                SET.add(arr[j]);
                j++;
            }
            output += ((j - i) * (j - i + 1)) / 2;
            SET.remove(arr[i]);
        }
        return output;
    }
    public static void main(String[] args)
    {
        int[] arr = { 3, 1, 2,1  };
        int n = arr.length;
        System.out.println(getLength(arr, n));
    }
}
13

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

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

Біз массивті айналып өтіп жатырмыз, және HashSet-ті қолдану кірістіруді және басқа амалдарды O (1) -де жүргізуге мүмкіндік береді. Осылайша біз қол жеткіземіз O (N) уақыт күрделілігі қайда «N» - бұл массивтегі элементтер саны.

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

Біз тек N элементті ғана сақтағандықтан, сызықтық кеңістікке қол жеткіздік. O (N) қайда «N» - бұл массивтегі элементтер саны