Найти максимальное неповторяемое значение в массиве со временем ~ O (N) - PullRequest
Новая
       9

Найти максимальное неповторяемое значение в массиве со временем ~ O (N)

0 голосов
/ 12 мая 2018

Как мы могли бы найти максимальное неповторяемое значение в массиве за время ~ O (N)

Я пытался сделать это в течение огромного времени, но я нашел только ~ O (2N): 

int solution(int[] A) {

    List<Integer> arr = new ArrayList<Integer>();
    Set<Integer> set = new HashSet<Integer>();

    int max = 0;

    for(int i = 0; i < A.length; i++) {

        if(!set.add(A[i])) arr.add(A[i]);

    }

    for(int i = 0; i < A.length; i++) {
        if (max < A[i] && !arr.contains(A[i])) max = A[i];
    }

    return max;

}

Можем ли мы сделать это немного быстрее?!

Ответы [ 3 ]

0 голосов
/ 12 мая 2018 
    int A[] = {5, 5, 3, 2, 3, 1};
    Map<Integer, Integer> map = new HashMap<>();

    for(int i : A) {
        Integer count = map.get(i);
        // according to the comments
        // map.merge(i, 1, Integer::sum)
        map.put(i, count == null ? 1 : count + 1);
    }

    int max = 0;
    for (Map.Entry<Integer, Integer> e : map.entrySet()) {
        if (e.getValue() == 1 && max < e.getKey()) {
            max = e.getKey();
        }
    }

    System.out.println(max);

Здесь вы сопоставляете каждое число с числом раз, которое оно присутствует в массиве.

В этом случае сложность составляет O (n).

И возможно только целое числомаксимально возможная реализация 

// this code for academic purpose only
// it can work only with integers less than
// 2^nextPowerOfTwo(array.lenght) as
// hash collision doesn't resolved
public static int nextPowerOfTwo(int value) {
    value--;
    value |= value >> 1;
    value |= value >> 2;
    value |= value >> 4;
    value |= value >> 8;
    value |= value >> 16;

    return ++value;
}

public static int findMaxUnique(int[] array) {
    final int hashSize = nextPowerOfTwo(array.length);
    final int[] hashArray = new int[hashSize];

    for (int n : array) {
        int hash = n ^ (n >>> 16);
        hash &= hashSize - 1;
        hashArray[hash]++;
    }

    int max = 0;
    for (int n : array) {
        int hash = n ^ (n >>> 16);
        hash &= hashSize - 1;
        if (hashArray[hash] == 1 && max < n) {
            max = n;
        }
    }

    return max;
}

public static void main(String[] args) {
    int[] array = {5, 4, 5, 3, 1, 5, 4, 0};
    System.out.println(findMaxUnique(array));
}
0 голосов
/ 12 мая 2018

Идея состоит в том, чтобы посчитать количество вхождений и сохранить его в древовидной карте.так как treeMap отсортирован, мы можем найти последнее (наибольшее) число, которое не повторяется (значение 1) 

//tree map is sorted... so the idea is to find the last item with value = 1
TreeMap<Integer,Integer> occurrence = new TreeMap<>();

//tabulate the number of occurrence of each key 
//O(2N)
Stream.of(array).forEach( key ->
    occurance.compute(key, (k, v) -> v == null ? 1 : v + 1));

//now that we have the treeMap with the number of occurrence, 
//we can find the last non-repeated value.


while(!occurance.isEmpty()){
  //iterate from the back up
  Map.Entry<Integer,Integer> le = occurance.pollLastEntry(); //or var if JAVA10
  if (le.getValue==1) return le.getKey(); 

}

//no unique numbers found
return Integer.MIN_VALUE;
0 голосов
/ 12 мая 2018

Вероятно, вы могли бы отсортировать ваш массив в порядке убывания, используя Radix sort , а затем перебрать его и проверить, не currentIndex == currentIndex + 1.

Это даст ваммаксимальная сложность O(n*x), которая в основном такая же, как O(n), если я не ошибаюсь, и все же лучше, чем фактическая O(n^2), которую вы используете

...