Գտեք բազմակի կրկնվող տարրերից որևէ մեկը միայն կարդալու զանգվածում  


Դժվարության մակարդակ Դժվար
Հաճախակի հարցնում են Capital One facebook Google Իսկապես Microsoft Pinterest
Դասավորություն Խանգարել

«Միայն կարդալու զանգվածում գտնել բազմակի կրկնվող տարրերից որևէ մեկը» խնդիրը նշում է, որ ենթադրում են, որ ձեզ տրվում է միայն ընթերցանության դասավորություն չափի (n + 1): Rayանգվածը պարունակում է 1-ից n ամբողջ թվեր: Ձեր խնդիրն է պարզել միայն կարդալու զանգվածի կրկնվող տարրերից որևէ մեկը:

Օրինակ  

Գտեք բազմակի կրկնվող տարրերից որևէ մեկը միայն կարդալու զանգվածումPin

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 / Squareroot) + 1:
  3. Ստեղծեք չափի տիրույթի զանգված:
  4. Հաշվեք և պահեք յուրաքանչյուր տարրի հաճախականությունը սրանով (freqCount [(arr [i] - 1) / Squareroot] ++):
  5. հավաքածու «Ընթացիկ արգելափակում» միջակայքում -1:
  6. Մինչ ես <range-1:
    1. Եթե ​​freqCount [i]> Squareroot, ապա կատարիր currentBlock = i և կոտրիր:
  7. Հայտարարել ա Քարտեզը.
  8. Երթևեկեք քարտեզում ՝ պատկանող տարրերի առկայությունը ստուգելու համար «Ընթացիկ արգելափակում».
    1. Դրանից հետո դրեք arr [i] և ավելացրեք քարտեզի բանալու արժեքի արժեքը:
    2. Եթե ​​ստեղնի արժեքը 1-ից մեծ է գտնվել, ապա վերադարձիր arr [i]:
  9. Այլ վերադարձ -1 (տարր չի գտնվել):

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

Մենք հարց ենք տվել ՝ պարզելու համար զանգվածում առկա կրկնվող տարրը, որում բոլոր ամբողջ թվերը տատանվում են 1-ից n և զանգվածի չափը n + 1: Քանի որ այն ցույց է տալիս մեկ կրկնվող տարրի առկայությունը, դրա համար էլ այն ունի n + 1 չափս:

Տես նաեւ,
Պայուսակի խնդիրը

Պարզ լուծում է ստեղծել HashMap և պահպանել տարրերից յուրաքանչյուրի հաճախականության հաշվարկը: Բայց այս լուծումը պահանջում է O (N) ժամանակ և O (N) տարածություն: Կարո՞ղ ենք սրանից լավ գործեր անել:

Կարող ենք օգտագործել այնպիսի մոտեցում, որը նման է քառակուսի արմատների քայքայման: Այս մոտեցումը կնվազեցնի մեր տիեզերական բարդությունը մինչև O (sqrt (N)): Մենք ստեղծում ենք sqrt (N) + 1. զանգվածի զանգված և շարունակում ենք մեծացնել արժեքներին համապատասխան ցուցանիշները ՝ arr (i-1) / sqrt (n) բանաձևի համաձայն: Դա անելուց հետո մենք, անշուշտ, կպարզենք մի ցուցիչ, որն ունի sqrt (N) - ից մեծ հաճախականություն: Այժմ մենք կօգտագործենք նախորդ մեթոդը, բայց միայն այս տիրույթին պատկանող տարրերի համար:

Հեշինգ և որոշ հիմնարար մաթեմատիկա օգտագործվում է խնդրի լուծման համար: Կրկնվող տարրը պարզելու համար մենք կանցկացնենք զանգված և զանգվածի 1 չափից պակաս XNUMX արժեք: Եկեք օրինակ վերցնենք դա լուծելու համար.

Rayանգված [] = {6, 1, 2, 3, 5, 4, 6}, n = 6

Եթե ​​չափը լինի n + 1 այդ ժամանակ մենք կանցնենք n դրան Այժմ մենք պետք է պարզենք դրա քառակուսի արմատը n և պահեք այն ինչ-որ փոփոխական արտահայտությամբ քառակուսի արմատ= 2 Այժմ մենք պետք է պարզենք զանգվածի տիրույթը: Մենք պատրաստվում ենք ստեղծել զանգվածային ասույթ freqCount 'range = 4' չափի, մենք կգտնենք միջակայքը ըստ (n / squareroot) + 1-ի:

Մենք հաշվելու ենք յուրաքանչյուր տարրի հաճախականությունները զանգվածի տիրույթում, որը մենք ստեղծել ենք անցնելով: Ամեն անգամ անցնելիս մենք հետևելու ենք freCount [(arr (i) -1) / squareroot] ++ - ին:

Վերջիվերջո, մենք մեր freqCount զանգվածում կունենանք հետևյալ արժեքները.

Տես նաեւ,
Rayանգվածում գտեք ամենամեծ d- ն այնպես, որ a + b + c = d

հաճախականություն: [2,2,3,0]

Setting up ընթացիկ արգելափակում տատանվել -1-ի, այսինքն `3. Մենք կանցնենք այն freqCount զանգված Եթե ​​գտնենք արժեքը ավելի մեծ, քան քառակուսի արմատ զանգվածում Մենք գտնում ենք, որ freqCount- ի 2-րդ ինդեքսում և ներկայիս բլոկը դնում ենք i և break: Մենք կհայտարարենք ա հեշմապ և անցեք մուտքի զանգվածի յուրաքանչյուր տարր և ստուգեք, թե արդյոք տարրերից որևէ մեկը պատկանում է ընթացիկ Block- ին և sqaureroot- ին, եթե այո, ապա այն դնում ենք քարտեզի մեջ և վերադարձնում arr- ի այդ արժեքը [i]:

Մեր արդյունքը կլինի. 6

C ++ կոդ `միայն կարդալու զանգվածում գտնելու բազմակի կրկնվող տարրերից որևէ մեկը  

#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

Java կոդ ՝ միայն կարդալու զանգվածում բազմակի կրկնվող տարրերից որևէ մեկը գտնելու համար  

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

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

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

ՎՐԱ) որտեղ «Ն» (զանգվածի երկարությունը - 1) է, այսինքն, n - 1. Քանի որ մենք պետք է անցնենք բոլոր տարրերը:

Տես նաեւ,
Ամենաերկար աճող հաջորդական հետևանքները

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

sqrt (N) որտեղ «Ն» է (զանգվածի երկարությունը - 1), այսինքն, n-1: Ալգորիթմի բնույթի պատճառով: Նախ, մենք հաշվարկ կատարեցինք sqrt- ի (N) չափին հավասար հատվածների համար: