Подпасоли со изразени елементи


Ниво на тешкотија Медиум
Често прашувано во Cisco Бесплатно полнење Тајмс Интернет Zoho
Низа Хаш Хашинг

Изјава за проблем

„Под-низи со изразени елементи“ наведува дека ви е дадена низа цели елементи. Изјавата за проблемот бара да се најде збирот на должините на соседните под-низи кои ги имаат сите елементи различни едни од други.

пример

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

Објаснување: Под-низите се ⇒ (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.

Објаснување

Дадовме една број низа. Нашата задача е да ја откриеме збирот на должината на сите под-низи кои се соседни и имаат само посебни елементи. Useе користиме a Намести. Сет обезбедува функција за отстранување на копирани или вообичаени елементи од еден сет. Поставете j на 0 и излезете на 0.

Започнете со пресекување на низата и користете a додека јамка. Поставете ја вредноста на j на 0 и внатре додека јамка ќе ја поминеме јамката додека го зголемуваме j. Поставете некои услови на неа, додека j е помала од n, т.е. должината на низата и исто така ако се утврди дека Set ја содржи вредноста на arr [j]. Да разгледаме пример:

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

Beе ја прелистуваме низата со избирање на секој елемент истовремено, да претпоставиме дека ќе избереме 3 за прв пат, во arr [j], идејата е да се задржи надворешната јамка константна само за некое време, оваа 3 ќе започне во додека јамка, бидејќи j е иницијализиран како 0, и множеството не содржи 3 за прв пат, па затоа ќе влезе во a додека јамка и внесете го arr [j] значи 3 и зголемете го j ++, тој ќе го избере следниот елемент како 1, Намести не го содржи така што ќе биде вметнат во сет, потоа доаѓа 2, а потоа доаѓа 1, но овој пат, 1 веќе е во јамка, па ќе излезе од додека јамка.

Сега кога ќе излеземе од јамката имаме зголемена вредност на 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 овозможува извршување вметнување и други вакви операции во О (1). Така постигнуваме НА) временска сложеност каде „Н“ е бројот на елементи во низата.

Комплексноста на просторот

Бидејќи зачувавме само N елементи, постигнавме линеарна просторна сложеност. НА) каде „Н“ е бројот на елементи во низата