Вот рекурсивный алгоритм, который будет возвращать абсолютные уникальные записи в списке за один проход, то есть за O (n) время.Он основан на том факте, что массив отсортирован и не использует java.util.Set.
Рассмотрим этот пример массива {-5, -5, -3,0,1,3}
- Поскольку массив отсортирован, один из двух элементов на каждом конце массива будет иметь абсолютное наибольшее значение: -5
- Опять же, поскольку массив отсортирован, если этот элементесли будет совпадение, он будет его соседом или соседями для нескольких совпадений.
- Так что для -5 мы делаем одну проверку с его соседом: они равны.-5 является дубликатом, поэтому удалите его, не увеличивайте наш текущий итог и повторяйте.
{- 5, -3,0,1,3} Теперь мы выбираем -5, его уникальныйпоэтому увеличьте промежуточный итог до 1, а затем удалите его.
{- 3,0,1,3} Если два конца имеют одинаковые абсолютные значения, просто удалите один, это не имеет значения, который, так же как еготолько один.Скажи первый.Мы не увеличиваем нашу промежуточную сумму, потому что значение, которое мы удалили, было дубликатом.
{0,1,3} Теперь мы выбираем 3, его уникальная промежуточная сумма равна 2.
{0,1} Выберите 1, его уникальный промежуточный итог 3.
{0} Размер равен 1, значение уникально, увеличьте промежуточный итог и верните его.4 Правильно!
package com.codility.tests;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class AbsDistinct {
/**
* Count the number of absolute distinct elements in an array.
* The array is sorted in ascending order.
*/
private static int countAbsDistinct(List<Integer> list, int count) {
int lastIndex = list.size() - 1;
if (lastIndex == -1) { // zero size list, terminate
return 0;
}
if (lastIndex == 0) { // one element list, terminate
return ++count;
}
if (Math.abs(list.get(0)) == Math.abs(list.get(lastIndex))) {
// doesn't matter which end is removed, but to remove _only_ 1
list.remove(0);
} else if (Math.abs(list.get(0)) > Math.abs(list.get(lastIndex))) {
// if different to its nighbour, its unique hence count it
if (list.get(0) != list.get(1)) {
count++;
}
// now that its been accounted for, remove it
list.remove(0);
} else {
// same logic but for the other end of the list
if (list.get(lastIndex) != list.get(lastIndex - 1)) {
count++;
}
list.remove(lastIndex);
}
return countAbsDistinct(list, count);
}
public static void main(String[] args) {
if (args.length == 0) { // just run the tests
List<Integer> testList = new ArrayList<Integer>(Arrays.asList(-9, -6, -5, -5, -5, -5, -3, -3, 0, 0, 1, 5, 6, 7, 7, 8));
List<Integer> empty = new ArrayList<Integer>();
List<Integer> singleElement = new ArrayList<Integer>(Arrays.asList(1));
List<Integer> sameElement = new ArrayList<Integer>(Arrays.asList(1, 1, 1, 1, 1, 1));
System.out.println("test array: " + countAbsDistinct(testList, 0));
System.out.println("empty array: " + countAbsDistinct(empty, 0));
System.out.println("single element array: " + countAbsDistinct(singleElement, 0));
System.out.println("same element array: " + countAbsDistinct(sameElement, 0));
} else {
List<String> argStringList = new ArrayList<String>(Arrays.asList(args));
List<Integer> argList = new ArrayList<Integer>();
for (String s : argStringList) {
argList.add(Integer.parseInt(s));
}
System.out.println("argument array: " + countAbsDistinct(argList, 0));
}
}
}