Задача Array Search [Workshop 4 - Arrays]

preparation

#1

Здравейте, колеги

Опитвам се да използвам подход за решаването на тази задача, който Judge не приема, но всичко работи наред при мен.

Идеята ми е да използвам минимално количество код, като работя директно по първоначалния String[] масив при user input, премахвайки всички дубликати чрез HashSet.

След това for/each loop върти String variable до length-а на String[] масива, докато вътре в него while loop проверява дали прочистения от дубликати HashSet не съдържа въпросния String variable. И ако това е така, добавяме String variable-a (което реално е номерче под формата на String) в празен ArrayList missingNumbers.

После просто представяме missingNumbers със String join(), за да му добавим запетайки.

Това е основната част от кода, пълният код тук (обновено решение - виж долу):

/*
Обновление 20.07.19 Долният код е действително грешен, просто аз съм гледал друг output заради погрешни настройки в InteliJ. По-долу в темата намираме алтернативно решение на тази задача. Междувременно, няколко дни след това открих грешката в моя код по-долу (смених for/each loop със стандартен for loop) и обнових горния линк с въпросното решение. Така че в тази тема има две решения на тази задача :wink:
*/

/*
Обновление 21.07.19 Разбрах причината долния код да е грешен - iterator variable-a при for/each loops е винаги item от самия Array/ArrayList, който той повтаря. Следователно, питането в моя while loop дали въпросния variable не се съдържа в изчистения от дубликати HashSet е безмислено - защото той винаги се съдържа в HashSet-а.

Да речем, пишем: 1,2,3,3,5. HashSet-а премахва двойната тройка и оставя 1,2,3,5. После чрез for/each loop-a минаваме през първоначалния Array от 1,2,3,3,5 (а не от 1 до 5 както аз си мислих) - и питаме дали тези числа не се съдържат в HashSet-a. Затова и получавах празен output от Judge, защото тези числа винаги се съдържат там.
*/

Scanner userInput = new Scanner(System.in);
String[] numbers = userInput.nextLine().split(",");
ArrayList<String> missingNumbers = new ArrayList<>();
HashSet<String> removeDup = new HashSet<>(Arrays.asList(numbers));

for (String strTemp : numbers) {
while (!removeDup.contains(strTemp)) {
missingNumbers.add(strTemp); }
}
System.out.println(missingNumbers.toString().join(",", missingNumbers));

Judge ми дава, че вадя празен output:
ArraySearch

Ще се радвам, някой да помогне да решим загадката!

Благодаря предварително!

Поздрави,
Петър


#2

Здравей Колега,

Моя съвет е заместо HashSet да използваш List (може и List-int-, както и List-string-).
Приложено ти изпращам решение, почти като твоето:
https://pastebin.com/HW74dNR8

Според мен, този strTemp те чупи на някой граничен кейс.

Като се загледах в кода, дори този .Distinct ще ни е излишен.

Поздрави,
Мишо


#3

Колега,

Пробвай да въведеш 0 като input и виж дали ще ти изпринти 1.
Подозирам, че най вероятно там се чупи и затова не ти минават останалите кейсове.

Лека нощ :slight_smile:


#4

Здравей, Мишо

Благодаря много за твоя код, научих нови неща!

Действително е възможно проблемът да е в нулите, защото забелязвам, че при написването на две нули, програмата показва 1,2 (а би трябвало да покаже само едно число, 1, защото дубликатът е само един).

От друга страна обаче, други решения, които минават на 100%, се държат по същия начин с нули и не работят въобще с отрицателни числа.

Така че мисля, че проблемът в горния код е може би другаде?

Твоят код на Java е всъщност още по-кратък (пълен код тук):

Scanner userInput = new Scanner(System.in);
ArrayList<String> list = new ArrayList<>(Arrays.asList(userInput.nextLine().split(",")));
ArrayList<String> missingNumbers = new ArrayList<>();
for (int i = 0; i < list.size(); i++) {
if (!list.contains(i)) {
missingNumbers.add(String.valueOf(i)); }
}
System.out.println(missingNumbers.toString().join(",", missingNumbers));

Спестяването произхожда от добавянето на Scanner input директно в ArrayList, вместо да правим първо масив за това. Освен това не ползваме HashSet и не премахваме дубликатите по никакъв начин. Аз също виждам логиката в това, защото за да намерим липсващото/ите число/а от поредица 1…N, можем просто да преброим от 1 до N, и да видим кои числа липсват.

Твоето решение минава също всички примери, но получава следния отговор:

nodup

Ще се радвам на някакви идеи :slight_smile:

Поздрави!
Петър


#5

Здравей :slight_smile:
Array е zero-based, a броенето започва от 1.
И още една насока: провери какво е поведението на този if (!list.contains(i))

Ако не я подкраш и все още имаш затруднения пиши :wink:

Хубав ден,
Диди


#6

Явно има друг проблем, понеже при мен минава 100/100 всички кейсове с този код.


#7

Здравей Диана,

Индексацията започна от 0 да, но counta започва от 1(ако имам 1 елемент Count == 1 а не Count == 0).

Така ако имам лист със 3 елемта ще завъртя 1/3 , 2/3 , 3/3 и ще проверя дали имам 1 2 3, ако не ще ги запиша.

if (!array.Contains(i)) - проверява в целия лист дали има такъв елемент, а не на дадения индекс.

Ако започна от 0, ще проверя дали имам 0 1 2 и задачата ще се счупи.

Поздрави,
Мишо


#8

Да разбирам, че пускате един и същ код към judge и единия път минава без грешка, а другия фейлва на първия тест?


#9

Здравейте,

Наистина бях дефинирал погрешно итерацията на for loop-a - сега кодът би трябвало да е идентичен?

Получавам следната грешка аз:

newest


#10

Здравей,
с този contains ти сравняваш String и int в момента
смени това >> if (!list.contains(String.valueOf(i)))
и би трябвало да работи.

Поздрави!


#11

Благодаря ви много, много неща научих!

Всичко работи отлично сега.

Хубав ден на всички!

Поздрави,
Петър