Array Duplicate Efficiency Riddle

Yaqinda AP Computer Science A da bizning sinfimiz yaqinda massivlar haqida bilib oldi. O'qituvchimiz bizga bir ish topib berdi. Aytaylik, sizda 20 ta raqam bor, 10dan 100gacha. (bu raqamlar skanerlar yordamida boshqa fayldan to'plangan)

Har bir raqam o'qilayotgandagina, agar raqamni o'qigan raqamning takroriyligi bo'lmasa, raqamni chop etishimiz kerak. Mana, mana bu erda. Muammoni hal qilish uchun mumkin bo'lgan eng kichik qatorni ishlatishimiz kerak.

Bu mening haqiqiy muammom. Barcha yechimim 20 ta bo'sh joyga ega bo'lgan juda katta massivni talab qiladi.

Men qatorni ishlatishim kerak. Muammoni samarali echish uchun qo'llashimiz mumkin bo'lgan eng kichik qator nima bo'lar edi?

Kimdir usulni pseudocode (yoki so'zlar bilan) bilan izohlashi mumkin bo'lsa, u ajoyib bo'lar edi.

1
Uzunligi yoki xotirasida eng kichikmi?
qo'shib qo'ydi muallif shmosel, manba
Stack Overflow ga xush kelibsiz! Siz uy vazifasi yordamini so'rashingiz mumkin. Bizda bunday muammolar mavjud emas, shuning uchun quyidagi amallarni ko'rib chiqing: http://meta.stackoverflow.com/questions/334822/how-do-i-ask-and-answer-homework-questions/338845# 338845 "> dos va don'ts" dan foydalaning va shunga mos ravishda savolingizni tahrirlang. (Agar bu uy vazifasi bo'lmasa ham, maslahatni ko'rib chiqing.)
qo'shib qo'ydi muallif Joe C, manba

6 javoblar

Eng yomon holatda 19 sonli qatordan foydalanishimiz kerak. 19 Nima uchun? Quyidagi raqamlardan takroriylarni ajratish uchun har bir noyob raqamni eslab qolish kerak. Sizga 20 ta raqam kirayotganligini bilsangiz, lekin ko'pi bilan siz oxirgi raqamni saqlamaysiz. Yoki 20-sonli raqamlar paydo bo'ldi (u holda hech narsa qilmaysiz) yoki 20 raqam noyobdir (undan keyin uni chop eting va uni saqlab qo'yish kerak emas).

Aytgancha: Men 20 katta uzunligi qator deb bo'lmaydi:)

3
qo'shib qo'ydi
Nima uchun men buni yubordim? boshlanuvchilar uchun dasturiy kursida faqatgina massivlar haqida bilib oldim. . Men bu darsning o'qituvchisi o'quvchilarning har qanday murakkab echimini topishni xohlashiga shubha qilaman. Ehtimol, ular hech qanday operatsiyalar bilan tanishmaganlar. Nima uchun yuqoriga ko'tarilgan? Yoki bu birinchi javob bo'lgani yoki yuqoriga ko'taruvchilar ham xuddi shunday his qilishgani uchun. Ehtimol, ikkalasi ham. Yozuv uchun: BitSet javobini yuqoriga ko'tarib, bu bilan davom ettirdim.
qo'shib qo'ydi muallif Socowi, manba
Bu barcha elementlarni tejaydi. Ammo qator qatorini sezilarli darajada kamaytiradigan bir nechta javoblar mavjud. Ehtimol, nima uchun bu yuqoriga ko'tarilgan yoki hatto e'lon qilingan.
qo'shib qo'ydi muallif shmosel, manba

Agar sizning raqamlaringiz tamsayı bo'lsa: siz 10 dan 100 gacha bo'lgan masofaga ega bo'lasiz. Shunday qilib, qanday qadriyatlar o'qilganligini saqlash uchun 91 bit kerak. Java Long ning 64 biti bor. Shunday qilib, sizga ikkita uzunlikdagi bir qator kerak bo'ladi. Har bir bitni (ortiqcha bo'lganlar bundan mustasno) 10 dan 100 gacha bir raqamga qo'ying. Har ikkala uzunlikni ham 0 bilan boshlang. Agar raqam o'qilsa, o'qish qiymatiga teng keladigan bitni 1 ga o'rnatilganmi deb belgilansin. Ha bo'lsa, O'qish raqami ikki nusxadir, agar bit 1 ga o'rnatilmagan bo'lsa.

BitSet sinfining orqasidagi fikr. .

2
qo'shib qo'ydi
Agar kamroq xotiraga boradigan bo'lsangiz, siz 3 dyuymli qatordan foydalanishingiz mumkin.
qo'shib qo'ydi muallif shmosel, manba

Kirish kattaligi aniqlanganligi sababli siz texnik jihatdan qatorga ehtiyoj sezmaysiz, faqat 20 o'zgaruvchini e'lon qilishingiz mumkin. Biroq, bu aniq emas, deylik.

Boshqa javobda aytilganidek, eng yomon hol, aslida qatorda 19 ta uydir. Ammo, biz bu erda tamsayılar haqida gapirganda, ba'zi raqamlar vaqtinchalik intervalni tashkil etadigan yaxshi ish stsenariysi mavjud. Bunday holatda, siz eng yuqori va eng kam sonni eslab qolishingiz kerak, chunki bular orasida har qanday narsa ham dublikatdir. intervallarni qatoridan foydalanishingiz mumkin.

10 dan 100 gacha bo'lgan sonlar bilan raqamlar bir-biridan ajratilgan bo'lishi mumkin va eng yomon holatda siz hali ham 19 tadan araziga kerak. Lekin, eng yaxshi holat yuzaga keladi va barcha raqamlar bir-biriga bog'liq bo'lgan oraliqni hosil qiladi, keyin siz faqat 1 qatorli uyaga kerak.

O'zingiz hal qilmoqchi bo'lgan muammoni - elementni qo'shganda 1-bandning o'zida kengaytiriladigan qatordan ajralma hosil qilish, shu sababli zarur bo'lgan minimal hajmni ishlatishdir. ( ArrayList ga o'xshash, lekin hajmi kattaligiga kelsa hajmi kattalashadi).

1
qo'shib qo'ydi

Socowi bilan kelishish. Agar raqamlar soni ma'lum bo'lsa va Nga teng bo'lsa, dublikatlarni saqlab qo'yish uchun har doim N-1 qatoridan foydalanish mumkin. Kirishdan so'nggi element qabul qilingach va bu oxirgi element ekanligi ma'lum bo'lsa, bu oxirgi qiymatni ikki nusxadagi qatorda saqlashga hojat yo'q.

Yana bir fikr. Agar sizning raqamlaringiz kichik bo'lsa va [10: 100] diapazonida joylashgan bo'lsa, siz kamida 2 ta kichik sonni saqlash uchun Long raqamini ishlatishingiz mumkin va ikkilik yordamida ularni uzoq raqamdan chiqarib, kichik tamsayı qiymatlarini qaytarib olishingiz mumkin. Bunday holatda N/2 qatoridan foydalanish mumkin. Ammo bu qatorda yanada murakkabroq va ko'p xotirani saqlamaydi, faqatgina qator elementlarning soni kamayadi.

1
qo'shib qo'ydi

Oxirgi javobim sizga kerak bo'lgan narsalarni noto'g'ri tushundi, lekin men bu narsani o'zgartirdim, bu bitni almashtirish yordamida 5 ta elementni tashkil qiladi. Maksimal sonning 100 ekanligini bilganimiz uchun har bir indeksga to'rtta sonni (ko'p tarqoq) saqlashimiz mumkin.

    Random rand = new Random();

    int[] numbers = new int[5];
    int curNum;

    for (int i = 0; i < 20; i++) {

        curNum = rand.nextInt(100);

        System.out.println(curNum);

        boolean print = true;
        for (int x = 0; x < i; x++) {

            byte numberToCheck = ((byte) (numbers[(x - (x % 4))/4] >>> ((x%4) * 8)));

            if (numberToCheck == curNum) {

                print = false;

            }

        }

        if (print) {

            System.out.println("No Match: " + curNum);

        }

        int index = ((i - (i % 4))/4);
        numbers[index] = numbers[index] | (curNum << (((i % 4)) * 8));

    }

Mening tovushlarni olish uchun rand-dan foydalanaman, lekin uni brauzerda osongina o'zgartirish mumkin.

0
qo'shib qo'ydi
Menda ikkilangan operatsiyalar qanchalik yomon ekanligi haqida hech qanday tasavvurga ega emasman, chunki men ular bilan birinchi marta suhbatlashganman, lekin bu vazifani bajaradi. Mening so'nggi savolimga javob bergan odamlar meni juda bezovta qildilar, shuning uchun spektaklni ta'qib qilgan narsalarni aylantirmoq kerak edi.
qo'shib qo'ydi muallif Jdman1699, manba

Agar qator ishga tushirish vaqtida kattalikni o'zgartira olmasa, siz kopyalanmagan raqamlarni hisoblash va qatorni faqatgina ushbu raqamlarga qisman to'ldirish uchun birlashtiruvchi o'zgaruvchiga kerak.

Bu erda sherik kodli kod currentsize ni ishlatadi va qatorni qisman to'ldiradi.

Shu bilan bir qatorda, ish vaqtida o'lchamini o'zgartiradigan arrayList dan foydalanishingiz mumkin

final int LENGTH = 20;
double[] numbers = new double[LENGTH];

int currentSize = 0;
Scanner in = new Scanner(System.in);
while (in.hasNextDouble()){
 if (currentSize < numbers.length){
 numbers[currentSize] = in.nextDouble();
 currentSize++;
 }
}

Edit

Keling, currentSize dublikati bo'lmagan haqiqiy raqamlarni o'z ichiga oladi va ba'zi dublikatlar bo'lsa, barcha 20 ta elementni to'ldirmaysiz. Albatta raqamlarning ikki nusxasi yoki yo'qligini aniqlash uchun sizda ba'zi kod kerak.

0
qo'shib qo'ydi