Найти дубликат в массиве
Имея доступный только для чтения массив целых чисел n + 1 между 1 и n, найдите одно число, которое повторяется за линейное время, используя меньше, чем пространство O(n), и проходя поток последовательно O(1) раз. Если возможных ответов несколько, выведите любой.
Если дубликата нет, вывести -1
Вход: [3 4 1 4 1]
Выход: 1 or 4
Почему следующий код не работает?
public int repeatedNumber(final List<Integer> a) {
Collections.sort(a);
for (int i = 0; i < a.size() - 1; i++) {
if (a.get(i) == a.get(i + 1)) {
return a.get(i);
}
}
return -1;
}
Пожалуйста, не просите пересмотра, иначе Зачем ваш код не работает. Это значит, что «нас» просят сделать то, что, как минимум, от вас ожидается.
Также, пожалуйста, пометьте его на определенном языке. Похоже, вы используете Java; добавьте его или правильный.
Не думаю, что мне нужно просматривать весь список, потому что он уже отсортирован. Если какое-либо целое число повторяется, оно будет в соседней позиции, и код его поймает.
Извините, я здесь новенький. Я просто не понимаю, почему этот подход не работает.
Какой результат вы получаете? -1?
Для некоторых тестовых случаев, которые я пробовал сам, я получаю правильный результат, но для тестового примера компилятором я получаю -1, что неверно.
Приведите примеры ввода / вывода. Желательно, чтобы вы проявили некоторые усилия и рассудительность. Как => «Я пробовал [это] и ожидал [этого], но получил [что-то другое]». Это будет иметь большое значение.
@JatinGupta проверьте ответ, который вы не получите 4, потому что сначала повторяется 1 из-за .sort (), а затем функция завершается
Компилятор тестового примера представляет собой массив из 600 элементов. Не могу поместить это здесь из-за ограничения на количество символов
Да, я знаю @AviSangray .. По моему коду, я получу только наименьший повторяющийся номер. Вопрос гласит, что я могу вернуть любое повторяющееся число, и вывод будет действительным.
Код @JatinGupta работает нормально. он делает выводы 1. Не могли бы вы подробнее рассказать о своей проблеме
Компилятор тестового примера представляет собой массив из 600 элементов. В то время как вывод должен быть 134 в этом списке, но каким-то образом мой код возвращает -1. Не могу поместить это здесь из-за ограничения на количество символов
Ответы 2
Может быть
public int repeatedNumber(final List<Integer> a) {
Collections.sort(a);
for (int i = 1; i < a.size(); i++) {
if (a.get(i) == a.get(i - 1)) {
return a.get(i);
}
}
return -1;
}
Вы получите исключение Index out of bounds, если это Java с вашим кодом. Во-вторых, я бы размер кеша.
Хотя для меня это похоже на домашнее задание.
@ChiefTwoPencils ... и нет, дружище. Просто наблюдение. Об этом много говорят в мета, поэтому я не стану начинать новую.
Этот фрагмент бесполезен. Вы только предполагаете без оснований для предположений. Они не знают, почему вас волнует, что это домашнее задание, а вы, похоже, говорите от имени нас.
Не домашнее задание. Я изучаю структуры данных и алгоритмы для собеседований и ломаю голову около часа над этим. Я думаю, что моя логика верна, но тестовый пример не запущен.
@ChiefTwoPencils LOL, почему ты думаешь, что я говорю за кого-то еще, кроме себя? Это риторический вопрос, если у вас возникло искушение ответить .... Как бы то ни было, спокойной ночи.
@JatinGupta Хорошо, тогда извините.
Вы делаете бессмысленный комментарий без видимой причины, чтобы, не понимая, подорвать их сообщение. Вы можете не осознавать или не беспокоиться, но когда вы публикуете здесь или взаимодействуете с другими пользователями, вы представляете сообщество; вы представляете нас. Попался, дешевый выстрел, или как вы хотите, чтобы это было сказано.
так что две вещи: - используйте только .size () вместо .size () - 1
public static int repeatedNumber(final List<Integer> a) {
Collections.sort(a);
for (int i = 0; i < a.size(); i++) {
if (a.get(i) == a.get(i + 1)) {
return a.get(i);
}
}
return -1;
}
Integer listy[] = {3,4,1,4,1 };
List iyu = new ArrayList(Arrays.asList(listy));
System.out.println(repeatedNumber(iyu));
в любом случае вы не получите 4 вывода, потому что он возвращает (выходит) при совпадении «1», поэтому не достигает 4 в списке и ты не будешь
Мне нужно вернуть только один повторяющийся номер. Мой код всегда будет возвращать наименьшее повторяющееся число.
@JatinGupta: почему бы вам не попробовать посмотреть вывод для каждой итерации и проверить, чтобы увидеть System.out.println (a.get (i) ":" a.get (i + 1));
@JatinGupta, а также выведите список, чтобы убедиться, что он отсортирован. просто удобная отладка
Хорошо, спасибо, попробую. Но я снова прочитал вопрос, и в нем говорится, что этот список доступен только для чтения, поэтому я думаю, что его нельзя изменять каким-либо образом, включая сортировку, и поэтому компилятор показывает ошибку
потому что вы не повторяете значения для сравнения по всему набору