ਇੱਕ ਐਰੇ ਵਿੱਚ ਨਾਲ ਲੱਗਦੇ ਤੱਤ ਵੱਖਰੇ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਸੌਖੀ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ Coursera ਡੀਈ ਸ਼ਾ ਵਾਧੇ IBM ਕੁਲਿਜ਼ਾ ਨਾਗਰੋ ਓਪੇਰਾ ਓਏ ਕਮਰੇ ਜੋਹੋ
ਅਰੇ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

ਮੰਨ ਲਓ ਸਾਡੇ ਕੋਲ ਏ ਪੂਰਨ ਅੰਕ ਐਰੇ. ਸਮੱਸਿਆ "ਐਰੇ ਵਿੱਚ ਵੱਖਰੇ ਨਾਲ ਜੁੜੇ ਤੱਤ" ਇਹ ਨਿਰਧਾਰਤ ਕਰਨ ਲਈ ਪੁੱਛਦੀ ਹੈ ਕਿ ਕੀ ਐਰੇ ਪ੍ਰਾਪਤ ਕਰਨਾ ਸੰਭਵ ਹੈ ਜਿਸ ਵਿੱਚ ਸਾਰੇ ਨਾਲ ਲੱਗਦੇ ਨੰਬਰ ਵੱਖਰੇ ਹਨ ਜਾਂ ਨਹੀਂ, ਜੇਕਰ ਇੱਕ ਐਰੇ ਵਿੱਚ ਦੋ ਨਾਲ ਲੱਗਦੇ ਜਾਂ ਗੁਆਂ neighborੀ ਤੱਤਾਂ ਨੂੰ ਬਦਲਣਾ ਸੰਭਵ ਹੈ ਤਾਂ "ਹਾਂ ਹਾਂ. ”ਜਾਂ“ ਨਹੀਂ ”ਪਰਿੰਟ ਕਰੋ।

ਉਦਾਹਰਨ

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

ਇਸ ਉਦਾਹਰਣ ਵਿੱਚ, ਅਸੀਂ ਏਰ [2] ਅਤੇ ਏਰ [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 ਨੰਬਰ ਦੀ ਇੱਕ ਐਰੇ ਹੈ, ਜਿਸ ਵਿਚ ਉਨ੍ਹਾਂ ਵਿਚੋਂ ਦੋ ਐਰੇ ਵਿਚ ਦੋ ਵਾਰ ਆਈਆਂ ਸਨ ਅਤੇ ਇਕ ਹੋਰ ਨੰਬਰ ਇਕ ਵਾਰ ਆਇਆ. ਇਸ ਲਈ ਅਸੀਂ ਐਰੇ ਦੇ ਹਰੇਕ ਐਲੀਮੈਂਟ ਦੀ ਬਾਰੰਬਾਰਤਾ ਨੂੰ ਸਟੋਰ ਕਰਾਂਗੇ. ਤੱਤ ਦੀਆਂ ਸਾਰੀਆਂ ਬਾਰੰਬਾਰਤਾ ਨੂੰ ਸਟੋਰ ਕਰਨ ਤੋਂ ਬਾਅਦ. ਅਸੀਂ ਮੈਕਸਫ੍ਰੇਕ ਵੇਰੀਏਬਲ ਨੂੰ 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

ਐਰੇ ਦੀ ਸਮੱਸਿਆ ਵਿੱਚ ਵੱਖਰੇ ਨਾਲ ਲੱਗਦੇ ਤੱਤ ਲਈ ਜਾਵਾ ਕੋਡ

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

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਹੇ (n) ਜਿੱਥੇ ਕਿ “ਐਨ” ਐਰੇ ਵਿਚਲੇ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਹੈ. ਕਿਉਂਕਿ ਅਸੀਂ ਹਾਸ਼ਮੈਪ ਦੀ ਵਰਤੋਂ ਕੀਤੀ ਹੈ ਅਸੀਂ ਰੇਖਿਕ ਸਮੇਂ ਦੀ ਜਟਿਲਤਾ ਨੂੰ ਪ੍ਰਾਪਤ ਕਰਨ ਦੇ ਯੋਗ ਹਾਂ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਹੇ (n) ਜਿੱਥੇ ਕਿ “ਐਨ” ਐਰੇ ਵਿਚਲੇ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਹੈ. ਜਿਵੇਂ ਕਿ ਅਸੀਂ ਹੈਸ਼ਮੈਪ ਦੀ ਵਰਤੋਂ ਕੀਤੀ ਹੈ ਅਸੀਂ ਤੱਤ ਦੇ ਫ੍ਰੀਕੁਐਂਸੀ ਸਟੋਰ ਕਰ ਰਹੇ ਸੀ. ਅਤੇ ਸਭ ਤੋਂ ਬੁਰੀ ਸਥਿਤੀ ਵਿੱਚ ਸਾਰੇ ਵੱਖ ਵੱਖ ਤੱਤ ਹੋ ਸਕਦੇ ਹਨ. ਫਿਰ ਸਾਡੇ ਕੋਲ N ਕੁੰਜੀ-ਮੁੱਲ ਦੀਆਂ ਜੋੜੀਆਂ ਹੋਣਗੀਆਂ. ਇਸ ਲਈ ਸਾਡੇ ਕੋਲ ਓ (ਐਨ) ਸਪੇਸ ਗੁੰਝਲਤਾ ਹੈ.