Найти элемент большинства в массиве

Question

решение 1: нет hashmap

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[(nums.length/2)];
    }
}

Решение 2: HashMap

class Solution {
    public int majorityElement(int[] nums) {
        for(int i:nums){
            if(hm.containsKey(i)){
                int cnt=hm.get(i);
                if(cnt+1>nums.length/2) return i;
                hm.replace(i,cnt+1);
            }
            else{
                if(1> nums.length/2) return i;
                hm.put(i,1);
            }
        }
        return -1;
    }
}

Какое решение быстрее и почему?Какова сложность каждого решения?

Вопрос:

Учитывая массив размера n, найдите элемент контрольного числа.Элемент контрольного пакета - это элемент, который появляется более ⌊ n / 2 2 раз.

Можно предположить, что массив не пустой, а элемент контрольного пакета всегда существует в массиве.

Answer 1

Я думаю, что решение № 2 с использованием HashMap быстрее.

В решении № 1 вы сортируете весь массив, который в худшем случае будет иметь сложность около O (nlogn).

Находясь в решении №2, вы просто делаете один проход массива, поэтому сложность составляет O (n).Вы даже ломаете (возвращаете), как только вы нашли элемент, считающий половину от количества элементов.Хотя это решение может потребовать некоторой дополнительной памяти, оно будет быстрее.

Обратите внимание, что я игнорирую время, затрачиваемое на containsKey(), get() и т. Д., Поскольку ключ Integer обеспечит постоянный произвольный доступ.То же самое и в случае доступа к элементу массива, например nums[index].