ਸਿਰਫ ਪੜਨ ਵਾਲੀ ਐਰੇ ਵਿੱਚ ਕੋਈ ਵੀ ਦੁਹਰਾਉਣ ਵਾਲੇ ਤੱਤ ਲੱਭੋ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਹਾਰਡ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਕੈਪੀਟਲ ਇਕ ਫੇਸਬੁੱਕ ਗੂਗਲ ਅਸਲ ਵਿੱਚ Microsoft ਦੇ ਕਿਰਾਏ ਨਿਰਦੇਸ਼ਿਕਾ
ਅਰੇ ਹੈਸ਼

ਸਮੱਸਿਆ "ਸਿਰਫ ਪੜਨ ਲਈ ਸਿਰਫ ਐਰੇ ਵਿੱਚ ਕਈ ਦੁਹਰਾਉਣ ਵਾਲੇ ਤੱਤ ਲੱਭੋ" ਕਹਿੰਦੀ ਹੈ ਕਿ ਮੰਨ ਲਓ ਕਿ ਤੁਹਾਨੂੰ ਸਿਰਫ-ਪੜ੍ਹਨ ਲਈ ਦਿੱਤਾ ਗਿਆ ਹੈ ਐਰੇ ਅਕਾਰ ਦਾ (n + 1). ਇੱਕ ਐਰੇ ਵਿਚ 1 ਤੋਂ n ਤੱਕ ਪੂਰਨ ਅੰਕ ਹੁੰਦੇ ਹਨ. ਤੁਹਾਡਾ ਕੰਮ ਸਿਰਫ-ਪੜ੍ਹਨ ਵਾਲੇ ਐਰੇ ਵਿਚਲੇ ਕਿਸੇ ਵੀ ਦੁਹਰਾਅ ਦੇ ਤੱਤ ਦਾ ਪਤਾ ਲਗਾਉਣਾ ਹੈ.

ਉਦਾਹਰਨ

ਸਿਰਫ ਪੜਨ ਵਾਲੀ ਐਰੇ ਵਿੱਚ ਕੋਈ ਵੀ ਦੁਹਰਾਉਣ ਵਾਲੇ ਤੱਤ ਲੱਭੋ

n = 5
arr[] = [1,2,4,2,3,5]
2

ਕਥਾ

ਸਿਰਫ-ਪੜਨ ਵਾਲੇ ਐਰੇ ਵਿਚ ਇਹ ਸਿਰਫ ਦੁਹਰਾਇਆ ਤੱਤ ਹੈ.

n = 9
arr[] = [1,2,4,6,3,5,7,8,9,9]
9

ਕਥਾ

ਸਿਰਫ-ਪੜਨ ਵਾਲੇ ਐਰੇ ਵਿਚ ਇਹ ਸਿਰਫ ਦੁਹਰਾਇਆ ਤੱਤ ਹੈ.

ਐਲਗੋਰਿਥਮ

  1. ਸੈੱਟ ਕਰੋ "ਵਰਗਮੂਲ" ਨੂੰ sqrt (n).
  2. (N / ਵਰਗਰੋਟ) + 1 ਲਈ ਰੇਂਜ ਸੈੱਟ ਕਰੋ.
  3. ਇੱਕ ਅਕਾਰ ਸੀਮਾ ਦੀ ਇੱਕ ਐਰੇ ਬਣਾਓ.
  4. ਇਸ ਦੇ ਨਾਲ ਹਰੇਕ ਤੱਤ ਦੀ ਬਾਰੰਬਾਰਤਾ ਨੂੰ ਗਿਣੋ ਅਤੇ ਸਟੋਰ ਕਰੋ (ਫ੍ਰੀਕਕਾਉਂਟ [(ਅਰਰ [i] - 1) / ਵਰਗਰੋਟ] ++).
  5. ਸੈੱਟ ਕਰੋ “ਕਰੰਟ ਬਲੌਕ” ਸੀਮਾ ਨੂੰ -1.
  6. ਜਦੋਂ ਕਿ ਮੈਂ <ਸੀਮਾ -1.
    1. ਜੇ ਫ੍ਰੀਕਕਾਉਂਟ [i]> ਵਰਗਕਾਰ ਹੈ, ਤਾਂ ਕਰੰਟਬੌਕ = i ਕਰੋ ਅਤੇ ਤੋੜੋ.
  7. ਘੋਸ਼ਣਾ ਏ ਫੋਲਡਰ ਨੂੰ.
  8. ਨਾਲ ਸਬੰਧਿਤ ਤੱਤਾਂ ਦੀ ਜਾਂਚ ਕਰਨ ਲਈ ਨਕਸ਼ੇ 'ਤੇ ਜਾਓ “ਕਰੰਟ ਬਲੌਕ”.
    1. ਫਿਰ ਏਰਰ [i] ਪਾਓ ਅਤੇ ਨਕਸ਼ੇ ਦੀ ਕੁੰਜੀ ਦੇ ਮੁੱਲ ਨੂੰ ਵਧਾਓ.
    2. ਜੇ ਇੱਕ ਕੁੰਜੀ ਦਾ ਮੁੱਲ 1 ਤੋਂ ਵੱਧ ਪਾਇਆ ਤਾਂ ਅਰਰ ਵਾਪਸ ਕਰੋ [i].
  9. ਹੋਰ ਵਾਪਸੀ -1 (ਕੋਈ ਤੱਤ ਨਹੀਂ ਮਿਲਿਆ).

ਕਥਾ

ਅਸੀਂ ਇੱਕ ਐਰੇ ਵਿੱਚ ਮੌਜੂਦ ਦੁਹਰਾਏ ਤੱਤ ਨੂੰ ਲੱਭਣ ਲਈ ਇੱਕ ਪ੍ਰਸ਼ਨ ਦਿੱਤਾ ਹੈ ਜਿਸ ਵਿੱਚ ਸਾਰੇ ਪੂਰਨ ਅੰਕ 1 ਤੋਂ n ਤੱਕ ਹੁੰਦੇ ਹਨ ਅਤੇ ਇੱਕ ਐਰੇ ਦਾ ਆਕਾਰ n + 1 ਹੁੰਦਾ ਹੈ. ਕਿਉਂਕਿ ਇਹ ਇਕ ਦੁਹਰਾਏ ਤੱਤ ਦੀ ਮੌਜੂਦਗੀ ਨੂੰ ਦਰਸਾਉਂਦਾ ਹੈ ਇਸ ਲਈ ਇਸਦਾ ਆਕਾਰ n + 1 ਹੁੰਦਾ ਹੈ.

ਇੱਕ ਸਧਾਰਣ ਹੱਲ ਹੈਸ਼ਮੈਪ ਤਿਆਰ ਕਰਨਾ ਅਤੇ ਹਰੇਕ ਤੱਤਾਂ ਦੀ ਬਾਰੰਬਾਰਤਾ ਦੀ ਗਿਣਤੀ ਰੱਖਣਾ ਹੈ. ਪਰ ਇਸ ਹੱਲ ਲਈ O (N) ਸਮਾਂ ਅਤੇ O (N) ਸਪੇਸ ਦੀ ਲੋੜ ਹੁੰਦੀ ਹੈ. ਕੀ ਅਸੀਂ ਇਸ ਤੋਂ ਵਧੀਆ ਕਰ ਸਕਦੇ ਹਾਂ?

ਅਸੀਂ ਅਜਿਹੀ ਪਹੁੰਚ ਵਰਤ ਸਕਦੇ ਹਾਂ ਜੋ ਵਰਗ ਵਰਗ ਦੇ ਸੜਨ ਵਰਗੀ ਹੈ. ਇਹ ਪਹੁੰਚ ਸਾਡੀ ਸਪੇਸ ਦੀ ਗੁੰਝਲਤਾ ਨੂੰ O (sqrt (N)) ਤੱਕ ਘਟਾ ਦੇਵੇਗੀ. ਅਸੀਂ ਸਾਈਜ਼ ਸਕੁਆਰਟ (ਐਨ) + 1 ਦੀ ਇਕ ਐਰੇ ਬਣਾਉਂਦੇ ਹਾਂ ਅਤੇ ਫਾਰਮੂਲਾ ਐਰ (ਆਈ -1) / ਸਕੁਐਰਟੀ (ਐਨ) ਦੇ ਅਨੁਸਾਰ ਮੁੱਲ ਦੇ ਅਨੁਕੂਲ ਸੂਚਕਾਂਕ ਨੂੰ ਵਧਾਉਂਦੇ ਰਹਿੰਦੇ ਹਾਂ. ਅਜਿਹਾ ਕਰਨ ਤੋਂ ਬਾਅਦ, ਅਸੀਂ ਨਿਸ਼ਚਤ ਰੂਪ ਤੋਂ ਇੱਕ ਸੂਚਕਾਂਕ ਦਾ ਪਤਾ ਲਗਾਵਾਂਗੇ ਜਿਸ ਦੀ ਬਾਰੰਬਾਰਤਾ sqrt (N) ਤੋਂ ਵੱਧ ਹੈ. ਹੁਣ ਅਸੀਂ ਪਿਛਲੇ methodੰਗ ਦੀ ਵਰਤੋਂ ਕਰਾਂਗੇ ਪਰ ਸਿਰਫ ਇਸ ਸ਼੍ਰੇਣੀ ਨਾਲ ਸਬੰਧਤ ਤੱਤਾਂ ਲਈ.

ਹੈਸ਼ਿੰਗ ਅਤੇ ਕੁਝ ਬੁਨਿਆਦੀ ਗਣਿਤ ਸਮੱਸਿਆ ਦੇ ਹੱਲ ਲਈ ਵਰਤੇ ਜਾਂਦੇ ਹਨ. ਦੁਹਰਾਏ ਤੱਤ ਦਾ ਪਤਾ ਲਗਾਉਣ ਲਈ ਅਸੀਂ ਇੱਕ ਐਰੇ ਅਤੇ ਇੱਕ ਐਰੇ ਪਾਸ ਕਰਾਂਗੇ ਜੋ ਐਰੇ ਦੇ ਆਕਾਰ ਤੋਂ ਘੱਟ ਹੈ. ਆਓ ਇਸ ਨੂੰ ਹੱਲ ਕਰਨ ਲਈ ਇੱਕ ਉਦਾਹਰਣ ਲੈਂਦੇ ਹਾਂ:

ਐਰੇ [] = {6, 1, 2, 3, 5, 4, 6}, ਐਨ = 6

ਜੇ ਅਕਾਰ ਹੈ n + 1 ਫਿਰ ਅਸੀਂ ਲੰਘ ਜਾਵਾਂਗੇ n ਇਸ ਨੂੰ ਕਰਨ ਲਈ. ਹੁਣ ਸਾਨੂੰ ਇਸਦੇ ਵਰਗ ਵਰਗ ਨੂੰ ਲੱਭਣਾ ਪਏਗਾ n ਅਤੇ ਇਸਨੂੰ ਕੁਝ ਵੇਰੀਏਬਲ 'ਤੇ ਸਟੋਰ ਕਰੋ ਵਰਗਮੂਲ= 2. ਹੁਣ ਸਾਨੂੰ ਐਰੇ ਦੀ ਸੀਮਾ ਦਾ ਪਤਾ ਲਗਾਉਣਾ ਹੈ. ਅਸੀ ਅਰੇ ਬਣਾਉਗੇ freqCount ਅਕਾਰ 'ਰੇਂਜ = 4' ਦੀ, ਅਸੀਂ ਰੇਜ਼ (n / ਵਰਗਰੋਟ) + 1 ਨਾਲ ਪਾਵਾਂਗੇ.

ਅਸੀਂ ਹਰ ਐਲੀਮੈਂਟ ਦੀ ਬਾਰੰਬਾਰਤਾ ਨੂੰ ਐਰੇ ਦੀ ਸੀਮਾ ਦੇ ਅੰਦਰ ਗਿਣਾਂਗੇ ਜੋ ਅਸੀਂ ਟਰੈਗਰਿੰਗ ਦੁਆਰਾ ਬਣਾਏ ਹਨ. ਹਰ ਵਾਰ ਜਦੋਂ ਅਸੀਂ ਲੰਘਦੇ ਹਾਂ ਅਸੀਂ ਫ੍ਰੀਕਾਉਂਟ [(ਅਰਰ (i) -1) / ਵਰਗੂੋਟ] ++ ਦੀ ਪਾਲਣਾ ਕਰਾਂਗੇ.

ਅਸੀ ਆਪਣੇ ਫ੍ਰੀਕਕਾਉਂਟ ਐਰੇ ਵਿੱਚ ਹੇਠਾਂ ਦਿੱਤੇ ਮੁੱਲ ਰੱਖਣਗੇ.

ਫ੍ਰੀਕਕਾਉਂਟ: [2,2,3,0]

ਸਥਾਪਤ ਕਰਨ ਮੌਜੂਦਾ ਬਲਾਕ ਸੀਮਾ ਹੈ -1 ਹੈ, ਜੋ ਕਿ 3 ਹੈ. ਸਾਨੂੰ ਪਾਰ ਕਰ ਦੇਵੇਗਾ freqCount ਐਰੇ. ਜੇ ਸਾਨੂੰ ਇਸ ਤੋਂ ਵੱਡਾ ਮੁੱਲ ਮਿਲ ਜਾਵੇ ਵਰਗਮੂਲ ਐਰੇ ਵਿੱਚ. ਅਸੀਂ ਵੇਖਦੇ ਹਾਂ ਕਿ ਫ੍ਰੀਕਕਾਉਂਟ ਦੇ ਦੂਜੇ ਇੰਡੈਕਸ 'ਤੇ ਅਤੇ ਮੌਜੂਦਾ ਬਲੌਕ ਨੂੰ ਆਈ ਅਤੇ ਬਰੇਕ ਸੈਟ ਕੀਤਾ. ਅਸੀਂ ਐਲਾਨ ਕਰਾਂਗੇ a ਹੈਸ਼ਮੈਪ ਅਤੇ ਇਨਪੁਟ ਐਰੇ ਦੇ ਹਰੇਕ ਐਲੀਮੈਂਟ ਨੂੰ ਟ੍ਰਾੱਰ ਕਰੋ ਅਤੇ ਜਾਂਚ ਕਰੋ ਕਿ ਕੀ ਕੋਈ ਐਲੀਮੈਂਟ ਮੌਜੂਦਾ ਬਲੌਕ ਅਤੇ ਸਕੁਏਰੂਰੋਟ ਨਾਲ ਸਬੰਧਤ ਹੈ, ਜੇ ਹਾਂ ਤਾਂ ਅਸੀਂ ਇਸ ਨੂੰ ਇਕ ਨਕਸ਼ੇ ਵਿਚ ਪਾਉਂਦੇ ਹਾਂ ਅਤੇ ਐਰ ਦਾ ਉਹ ਮੁੱਲ ਵਾਪਸ ਕਰਦੇ ਹਾਂ [i].

ਸਾਡੀ ਆਉਟਪੁੱਟ ਹੋਵੇਗੀ: 6

ਸੀ ++ ਕੋਡ ਸਿਰਫ ਰੀਰੇ ਐਰੇ ਵਿੱਚ ਦੁਹਰਾਓ ਵਾਲੇ ਕਈ ਗੁਣਾਂ ਵਿੱਚੋਂ ਕਿਸੇ ਇੱਕ ਨੂੰ ਲੱਭਣ ਲਈ

#include <unordered_map>
#include<iostream>
#include<math.h>
using namespace std;

int getRepeatedNumber(int arr[], int len)
{
    int squareroot = sqrt(len);
    int range = (len / squareroot) + 1;
    int count[range] = {0};

    for (int i = 0; i <= len; i++)
    {
        count[(arr[i] - 1) / squareroot]++;
    }
    int currentBlock = range - 1;
    for (int i = 0; i < range - 1; i++)
    {
        if (count[i] > squareroot)
        {
            currentBlock = i;
            break;
        }
    }
    unordered_map<int, int> m;
    for (int i = 0; i <= len; i++)
    {
        if ( ((currentBlock * squareroot) < arr[i]) && (arr[i] <= ((currentBlock + 1) * squareroot)))
        {
            m[arr[i]]++;
            if (m[arr[i]] > 1)
                return arr[i];
        }
    }
    return -1;
}
int main()
{
    int arr[] = { 6,1,2, 3, 5, 4, 6 };
    int n = 6;

    cout << "Repeated number(s) in the array is:"<< getRepeatedNumber(arr, n) << endl;
}
Repeated number(s) in the array is:6

ਜਾਵਾ ਕੋਡ ਸਿਰਫ ਪੜਨ ਵਾਲੀ ਐਰੇ ਵਿੱਚ ਕਈ ਦੁਹਰਾਓ ਤੱਤਾਂ ਨੂੰ ਲੱਭਣ ਲਈ

import java.util.*;
class arrayRepeatedElements
{
    public static int getRepeatedNumber(int[] arr, int len)
    {
        int squareroot = (int) Math.sqrt(len);
        int range = (len / squareroot) + 1;
        int freqCount[] = new int[range];
        for (int i = 0; i <= len; i++)
        {
            freqCount[(arr[i] - 1) / squareroot]++;
        }
        int currentBlock = range - 1;
        for (int i = 0; i < range - 1; i++)
        {
            if (freqCount[i] > squareroot)
            {
                currentBlock = i;
                break;
            }
        }
        HashMap<Integer, Integer> freq = new HashMap<>();
        for (int i = 0; i <= len; i++)
        {
            if ( ((currentBlock * squareroot ) < arr[i]) && ( arr[i] <= ((currentBlock + 1) * squareroot)))
            {
                freq.put(arr[i], 1);
                if (freq.get(arr[i])== 1)
                    return arr[i];
            }
        }
        return -1;
    }
    public static void main(String args[])
    {
        int[] arr = { 6,1, 2, 3, 5, 4, 6 };
        int n = 6;
        System.out.println("Repeated number(s) in the array is:"+getRepeatedNumber(arr, n));
    }
}
Repeated number(s) in the array is:6

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

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ) ਜਿੱਥੇ ਕਿ “ਐਨ” (ਐਰੇ ਦੀ ਲੰਬਾਈ - 1) ਭਾਵ ਐਨ - 1. ਹੈ ਕਿਉਂਕਿ ਸਾਨੂੰ ਸਾਰੇ ਤੱਤਾਂ ਨੂੰ ਪਾਰ ਕਰਨਾ ਹੈ.

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

ਵਰਗ (ਐਨ) ਜਿੱਥੇ ਕਿ “ਐਨ” (ਐਰੇ ਦੀ ਲੰਬਾਈ - 1) ਭਾਵ ਐਨ -1 ਹੈ. ਐਲਗੋਰਿਦਮ ਦੇ ਸੁਭਾਅ ਕਰਕੇ. ਪਹਿਲਾਂ, ਅਸੀਂ ਵਰਗ (ਐਨ) ਦੇ ਆਕਾਰ ਦੇ ਬਰਾਬਰ ਭਾਗਾਂ ਲਈ ਗਣਨਾ ਕੀਤੀ.