Массивдеги чектеш элементтер


Кыйынчылык деңгээли жеңил
Көп суралган Coursera DE Shaw селсаяктоо IBM Кулиза Нагарро опера OYO бөлмөлөр Zoho
согуштук тизме

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

Бизде ан бүтүн согуштук тизме. Массивдеги "Бөлүнүп турган чектеш элементтер" маселеси, эгерде мүмкүн болсо, массивдеги чектеш же коңшулаш эки элементти алмаштыруу менен бардык чектеш сандар айырмаланган массивди алууга болобу же жокпу деп сурайт, анда “Ооба ”Else print“ NO ”.

мисал

arr[] = { 3,5,5,3,5}
YES

Бул мисалда, аррды [2] жана arr [3] -ти 5 жана 2 деп алмаштырып, айырмаланган чектеш сандардын массивин алабыз.

Массивдеги чектеш элементтер

arr[] = {3 , 5,  3, 3 }
NO

түшүндүрүү

Маанилерди алмаштыргандан кийин деле керектүү массивди ала албайбыз.

Массивдеги өзүнчө чектеш элементтердин алгоритми

1. Declare a map.
2. Count and store the frequencies of each element of the array.
3. Set maxFreq to 0.
4. Get the maximum frequency of a number from the map.
5. Check if maxFreq is greater than the half-length of the array, means maxFreq >(n+1) / 2.
    1. If true, then print NO.
    2. Else print YES.

түшүндүрүү

Бизге бүтүндөй массив берилген. Бизден айырмаланган чектеш элементтер мүмкүн болгон массивди алабызбы же жокпу, сурадык. Демек, эгер мындай массивди колдонуу мүмкүн болбосо, анда ЖОК дегенди басып чыгарууга Ооба. Эми, керектүү массивди алуу үчүн канча номер алмаштырылышы керек экендигин текшеришибиз керек. Биз ар бир элементтин пайда болушун текшеришибиз керек, ошондой эле максималдуу көрүнүш массивдин узундугунун жарымынан көп болбошу керек. Эгерде массивдин узундугу 5 деп берилсе. Эгерде элемент массивде 3 көрүнүшкө ээ болсо. Андан кийин массивди биринчи, үчүнчү жана бешинчи позицияларда өзгөртүүгө болот. Ошентип, массивден чектеш элементтерди бөлүп алууга болот.

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

Ал үчүн биз картаны аралап, ар бир элементин текшериңиз, эгерде мурунку сакталган жыштыктан чоңураак болсо. Ушуну менен, биз жыштык катары максималдуу санга ээ болобуз жана ал жыштык массивдин узундугунун жарымынан чоң экендигин текшеребиз. Эгер чын болсо, ЖОКту баскыла, болбосо ООБА баскыла.

коду

Массив көйгөйүндөгү айырмаланган чектеш элементтер үчүн C ++ коду

#include<bits/stdc++.h>
using namespace std;
void areDistinctAdjacent(int a[], int n)
{
    unordered_map<int, int> MAP;
    for (int i = 0; i < n; ++i)
        MAP[a[i]]++;
    int maxFreq = 0;
    for (int i = 0; i < n; ++i)
        if (maxFreq < MAP[a[i]])
            maxFreq = MAP[a[i]];
    if (maxFreq > (n + 1) / 2)
        cout << "NO";
    else
        cout << "YES";
}
int main()
{
    int arr[] = { 3,5,5,3,5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    areDistinctAdjacent(arr, n);
    return 0;
}

 

YES

Массив көйгөйүндөгү айырмаланган чектеш элементтер үчүн Java коду

import java.util.HashMap;
import java.util.Map;

class adjacentDistinctElement
{
    static void areDistinctAdjacent(int a[], int n)
    {
        HashMap<Integer,Integer> MAP = new HashMap<Integer,Integer>();

        for (int i = 0; i < n; ++i)
        {
            if(MAP.containsKey(a[i]))
            {
                int x = MAP.get(a[i]) + 1;
                MAP.put(a[i],x);
            }
            else
            {
                MAP.put(a[i],1);
            }

        }
        int maxFreq = 0;

        for (int i = 0; i < n; ++i)
            if (maxFreq < MAP.get(a[i]))
                maxFreq = MAP.get(a[i]);

        if (maxFreq > (n + 1) / 2)
        {
            System.out.println("NO");
        }
        else
        {
            System.out.println("YES");
        }
    }
    public static void main (String[] args)
    {
        int arr[] = { 3,5,5,3,5 };
        int n = arr.length;
        areDistinctAdjacent(arr, n);
    }
}

YES

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

Убакыт татаалдыгы

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

Космостун татаалдыгы

O (N) кайда "N" массивдеги элементтердин саны. Хэшмапты колдонуп жатканда, биз элементтердин жыштыгын сактадык. Жаман учурда, ар кандай элементтер болушу мүмкүн. Андан кийин бизде ачкыч мааниси бар N жуптары болот. Ошентип, бизде O (N) мейкиндигинин татаалдыгы бар.