Online Majority Element In Subarray. Что-то я туплю
От: Codealot Земля  
Дата: 20.08.19 15:53
Оценка: 5 (1)
https://leetcode.com/problems/online-majority-element-in-subarray/

Мое решение:
    public class MajorityChecker
    {
        private int[] _arr;
        private int[] _counts;

        public MajorityChecker(int[] arr)
        {
            _arr = arr;
        }

        public int Query(int left, int right, int threshold)
        {
            _counts = new int[20001];

            for (var i = left; i <= right; i++)
            {
                var num = _arr[i];
                _counts[num]++;

                if (_counts[num] >= threshold)
                    return num;
            }

            return -1;
        }
    }


Ошибка: Time Limit Exceeded
Какие есть идеи, как сделать это быстрее?
Ад пуст, все бесы здесь.
Re: Online Majority Element In Subarray. Что-то я туплю
От: watchmaker  
Дата: 20.08.19 20:24
Оценка: +1
Здравствуйте, Codealot, Вы писали:

C>https://leetcode.com/problems/online-majority-element-in-subarray/


C>Какие есть идеи, как сделать это быстрее?


Из ограничений следует, что в массиве может быть не больше 142-х чисел, которые повторяются 142 или более раза.
Значит можно просто составить список частовстречающихся чисел на этапе препроцессинга. И если threshold >= 142, то проверять только их (через обычную сумму на отрезке), иначе если threshold < 142, то проверять твоим алгоритмом.
Re: Online Majority Element In Subarray. Что-то я туплю
От: StatujaLeha на правах ИМХО
Дата: 20.08.19 20:41
Оценка:
Здравствуйте, Codealot, Вы писали:

C>Какие есть идеи, как сделать это быстрее?


1. https://leetcode.com/problems/online-majority-element-in-subarray/discuss/
2. Снизу под задачей есть "Show Hint 1":

One strategy is the following: 1. Find a "majority candidate" : there's at most one value X that may appear more than half the time. We can sample repeatedly, or use a segment tree, or use block decomposition. 2. check whether the majority candidate appears more than threshhold times, using binary search. There's also another strategy: 1. Sort every value in order of how much they appear, and put that into a list 2. For each query with length L = right-left+1, if L < sqrt(N), check manually; otherwise, you can prove that you only need to check at most O(sqrt(N)) candidate values in the list for whether that candidate appears more than threshold times.

Re[2]: Online Majority Element In Subarray. Что-то я туплю
От: Codealot Земля  
Дата: 20.08.19 22:15
Оценка:
Здравствуйте, StatujaLeha, Вы писали:

SL>2. Снизу под задачей есть "Show Hint 1":

SL>

SL>One strategy is the following: 1. Find a "majority candidate" : there's at most one value X that may appear more than half the time. We can sample repeatedly, or use a segment tree, or use block decomposition. 2. check whether the majority candidate appears more than threshhold times, using binary search. There's also another strategy: 1. Sort every value in order of how much they appear, and put that into a list 2. For each query with length L = right-left+1, if L < sqrt(N), check manually; otherwise, you can prove that you only need to check at most O(sqrt(N)) candidate values in the list for whether that candidate appears more than threshold times.


Проглядел. То есть, подгонка под тестовые данные.
Ад пуст, все бесы здесь.
Re: Online Majority Element In Subarray. Что-то я туплю
От: rg45 СССР  
Дата: 06.09.19 06:08
Оценка:
Здравствуйте, Codealot, Вы писали:

C>https://leetcode.com/problems/online-majority-element-in-subarray/


C>
  Мое решение:
C>
C>    public class MajorityChecker
C>    {
C>        private int[] _arr;
C>        private int[] _counts;

C>        public MajorityChecker(int[] arr)
C>        {
C>            _arr = arr;
C>        }

C>        public int Query(int left, int right, int threshold)
C>        {
C>            _counts = new int[20001];

C>            for (var i = left; i <= right; i++)
C>            {
C>                var num = _arr[i];
C>                _counts[num]++;

C>                if (_counts[num] >= threshold)
C>                    return num;
C>            }

C>            return -1;
C>        }
C>    }
C>


C>Ошибка: Time Limit Exceeded

C>Какие есть идеи, как сделать это быстрее?

Я думаю, что фишка этой задачи — сделать максимум подготовительной работы в конструкторе с тем, чтобы максимально ускорить метод Query. Исходя из этого, работа конструктора не должна таймироваться, по идее. И лобовое решение, которое сразу же приходит в голову — построить квадратную матрицу, которая позволит по индексам начала и конца поддиапазона получить ответ за константное время. И конечно же, полная квадратная матрица не нужна, достаточно ее половины, включая диагональ, которая всегда будет содержать собственно сам массив. Всего (N^2 + N)/2 элементов. Следующий шаг — переход в рядах этой матрицы от массивов элементов к картам диапазонов одинаковых значений. Надеюсь, понятно изложил идею. Кодить лень, конечно же
--
Не можешь достичь желаемого — пожелай достигнутого.
Re: Online Majority Element In Subarray. Что-то я туплю
От: zubr Россия  
Дата: 09.09.19 17:22
Оценка:
Здравствуйте, Codealot, Вы писали:

C>https://leetcode.com/problems/online-majority-element-in-subarray/



C>Ошибка: Time Limit Exceeded

C>Какие есть идеи, как сделать это быстрее?

Нужна предподготовка данных. В данной задаче нужно создать необходимый класс в конструкторе, чтобы потом быстро обслуживать запросы.
Например, можно создать трехмерный массив [from,to,threshold], что конечно очень дорого в плане создания, зато потом очень дешево делать запросы.
Приведенная выше структура (трехмерный массив) это не решение, но скорее направление в сторону решения.
Re[2]: Online Majority Element In Subarray. Что-то я туплю
От: apachik  
Дата: 09.09.19 18:29
Оценка:
Здравствуйте, watchmaker, Вы писали:

W>Здравствуйте, Codealot, Вы писали:


C>>https://leetcode.com/problems/online-majority-element-in-subarray/


C>>Какие есть идеи, как сделать это быстрее?


W>Из ограничений следует, что в массиве может быть не больше 142-х чисел, которые повторяются 142 или более раза.

W>Значит можно просто составить список частовстречающихся чисел на этапе препроцессинга. И если threshold >= 142, то проверять только их (через обычную сумму на отрезке), иначе если threshold < 142, то проверять твоим алгоритмом.

вот это похоже на правду, ага.

посмотрел обсуждения, там сплошь и рядом рандомизированные "алгоритмы". мде
Но вообще там проходит линейный алгоритм большинства Бойера — Мура. в TL укладывается
https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B8%D0%BD%D1%81%D1%82%D0%B2%D0%B0_%D0%B3%D0%BE%D0%BB%D0%BE%D1%81%D0%BE%D0%B2_%D0%91%D0%BE%D0%B9%D0%B5%D1%80%D0%B0_%E2%80%94_%D0%9C%D1%83%D1%80%D0%B0
Отредактировано 09.09.2019 18:37 apachik . Предыдущая версия . Еще …
Отредактировано 09.09.2019 18:36 apachik . Предыдущая версия .
Re[2]: Online Majority Element In Subarray. Что-то я туплю
От: rg45 СССР  
Дата: 15.09.19 09:51
Оценка: +1
Здравствуйте, zubr, Вы писали:


Z>Нужна предподготовка данных. В данной задаче нужно создать необходимый класс в конструкторе, чтобы потом быстро обслуживать запросы.

Z>Например, можно создать трехмерный массив [from,to,threshold], что конечно очень дорого в плане создания, зато потом очень дешево делать запросы.
Z>Приведенная выше структура (трехмерный массив) это не решение, но скорее направление в сторону решения.

Третье измерение (threshold) не требуется. С учетом условия: 2 * threshold > right — left + 1, искомое число должно занимать более половины позиций поддиапазона. Такое число может быть либо одно, либо отсутствовать. Соответственно, достаточно двумерной коллекции (массив карт или массивов переменной длины), хранящим половину квадратной матрицы, элементом которой является пара {number/threshold} (-1/0 — для заведомо "пустых" поддиапазонов).
--
Не можешь достичь желаемого — пожелай достигнутого.
Отредактировано 15.09.2019 10:05 rg45 . Предыдущая версия . Еще …
Отредактировано 15.09.2019 10:00 rg45 . Предыдущая версия .
Отредактировано 15.09.2019 9:58 rg45 . Предыдущая версия .
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.