Пришло время опубликовать новую задачу по Java. Данное задание возникло в моей голове, когда мне понадобилось проверить умение человека работать с одномерными массивами и циклами. И поскольку тема проста, как угол дома, то и задача показалась мне такой же. Но как всегда, внешность обманчива и т. д.
Условие:
Задаем массив интов, произвольной длины. Пусть в нашем случае это будет {1, 2, 3, 1, 6, 8, 2}. Необходимо вывести все элементы массива, которые встречаются не более 1 раза.
Мое решение, которое как всегда, будет вам благодарно за советы по улучшению подхода:
1: int[] array = {1, 2, 3, 1, 6, 8, 2};
2: int length = array.length;
3: int[] resultArray = array;
4: for (int i = 0; i < length; i++) {
5: int counter = 0;
6: for (int j = 0; j < length; j++) {
7: if (array[i] == array[j])
8: counter++;
9: }
10: if (counter != 1) {
11: resultArray[i] = -999999;
12: }
13: }
14: for (int i = 0; i < length; i++)
15: if (resultArray[i] != -999999)
16: System.out.println(resultArray[i]+ " ");
Теперь немного поясню, что хотел этим кодом сказать:
Строка 1, 2 - по сути начальные условия
3 - копируем наш исходный массив, чтобы проводить над ним действия и не задеть оригинал
4 - начинается цикл, в котором мы вводим счетчик int counter = 0
6 - в новом цикле проводим проверку для каждого элемента из массива на равенство тому, который мы уже выбрали, в случае равенства увеличиваем счетчик на 1.
10 - если наш счетчик отличен от 1, то значит были повторения и наш элемент имеет клонов, тогда на место клона ставим число-индикатор (-999999)
14 - выводим наш результат и если встречаем -999999, то игнорируем его
UPDATE (Спасибо комментарию MightMortal):
1: int[] array = {9, 2, 1, 2, 3, 1, 6, 8, 2};
2: int length = array.length;
3: boolean[] resultArray = new boolean[length];
4: for (int i = 0; i < length; i++) {
5: int counter = 0;
6: for (int j = i; j < length; j++) {
7: if (array[i] == array[j])
8: counter++;
9: }
10: if (counter != 1) {
11: resultArray[i] = true;
12: }
13: }
14: for (int i = 0; i < length; i++)
15: if (resultArray[i] != true)
16: System.out.println(array[i]+ " ");
Я бы resultArray сделал булевым. Это даст немного экономии памяти(иногда это тоже нужно), а во вторых в это избавит от проблем с числом -999999, если оно есть в исходном массиве.
ОтветитьУдалитьПолностью согасен =)
УдалитьУ вас этот код работает как надо? о_О В нем есть ошибка - число 2 попадает в результат, хотя его там явно быть не должно. Ошибка в том, что учитываются только дубликаты, идущие после текущего индекса, в итоге для последней двойки в исходном массиве после нее дубликатов нет, хотя они есть до нее.
ОтветитьУдалитьВот мой вариант вашего измененного варианта:
int[] array = {9, 2, 1, 2, 3, 1, 6, 8, 2};
int length = array.length;
// элементы resultArray проинициализированны false - то, что нам надо
boolean[] resultArray = new boolean[length];
int comparisonCount = 0;
for (int i = 0; i < length; i++) {
if (resultArray[i]) {
// уже поняли, что этот элемент есть дубликат какого-то из предыдущих - игнорим
continue;
}
for (int j = i+1; j < length; j++) {
if (array[i] == array[j]) {
resultArray[i] = true;
resultArray[j] = true;
// хотелось бы вставить здесь break, да нельзя - нужно дойти до конца
}
}
}
for (int i = 0; i < length; i++)
if (resultArray[i] != true)
System.out.println(array[i]+ " ");
На собеседование зовете? :)
Зовем =)
УдалитьЭтот комментарий был удален автором.
ОтветитьУдалитьРешение за линейное время:
ОтветитьУдалитьpublic static Set<Integer> getOnetimeAppearedElements(int[] input) {
// Step 1: build dictionary which map elements of array to their frequency of appearance - execution time O(N)
Map<Integer, Integer> freqMap = new HashMap<>();
for (int i = 0; i < input.length; i++) {
freqMap.put(input[i], freqMap.containsKey(input[i]) ? freqMap.get(input[i]) + 1 : 1);
}
System.out.println(freqMap);
// Step 2: filter dictionary - execution time O(N)
Set<Integer> output = new HashSet<>();
for (Integer key : freqMap.keySet()) {
Integer value = freqMap.get(key);
if (value == 1) {
output.add(key);
}
}
return output;
}
public static void main(String[] args) {
Set<Integer> resSet = getOnetimeAppearedElements(new int[] {1, 2, 3, 1, 6, 8, 2});
System.out.println(resSet)
}