Rayանգվածի հստակ հարակից տարրերը


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Coursera ԴԵ Շոուն Զբոսանք IBM Կուլիզա Նագարո Օպերա OYO սենյակներ Zoho
Դասավորություն

Խնդիրի հայտարարություն

Ենթադրենք, որ մենք ունենք ամբողջ թիվ դասավորություն, «Rayանգվածի մեջ առանձնացված հարակից տարրեր» խնդիրը պահանջում է պարզել `հնարավոր է արդյոք ձեռք բերել այն զանգվածը, որում բոլոր հարակից թվերը տարբեր են, թե ոչ` զանգվածում փոխելով երկու հարակից կամ հարևան տարրերը, եթե դա հնարավոր է, ապա տպել «ԱՅՈ »Այլ տպել« ՈՉ »:

Օրինակ

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

Այս օրինակում մենք կարող ենք ստանալ հստակ հարակից թվերի զանգված ՝ փոխելով իրար [2] և ar [3], համապատասխանաբար 5 և 2:

Rayանգվածի հստակ հարակից տարրերը

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

բացատրություն

Մենք չենք կարող ստանալ ցանկալի զանգվածը նույնիսկ արժեքները փոխելուց հետո:

Gorանգվածի հստակ հարակից տարրերի ալգորիթմ

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անգվածային խնդրի մեջ առկա հարակից տարրերի համար 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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է: Քանի որ մենք օգտագործել ենք Hashmap- ը, մենք ի վիճակի ենք հասնել գծային ժամանակի բարդության:

Տիեզերական բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է: Քանի որ մենք օգտագործել ենք hashmap, մենք պահպանում էինք տարրերի հաճախականությունները: Եվ ամենավատ դեպքում կարող են լինել բոլոր տարբեր տարրերը: Դրանից հետո մենք կունենանք N ստեղնային արժեքի զույգեր: Այսպիսով, մենք ունենք O (N) տիեզերական բարդություն: