Массив размера n, с одним элементом n/2 времена
Да, вы можете, но я бы предложил сделать еще один шаг и сделать следующее:
void f<T, U>(T t, U u) where T : class
{
if (!t.GetType().IsAssignableFrom(u.GetType())) return;
T ut = u as T;
// can I assert that t is not null ?? Yes, you can
}
IsAssignableFrom следует прибить его для любого типа.
7 ответов
У меня есть скрытое подозрение, что это что-то вроде (в C #)
// We don't need an array
public int FindMostFrequentElement(IEnumerable<int> sequence)
{
// Initial value is irrelevant if sequence is non-empty,
// but keeps compiler happy.
int best = 0;
int count = 0;
foreach (int element in sequence)
{
if (count == 0)
{
best = element;
count = 1;
}
else
{
// Vote current choice up or down
count += (best == element) ? 1 : -1;
}
}
return best;
}
Это звучит маловероятно, но это так. ( Подтверждение в виде постскриптумного файла , предоставлено Бойером / Муром.)
int findLeader(int n, int* x){
int leader = x[0], c = 1, i;
for(i=1; i<n; i++){
if(c == 0){
leader = x[i];
c = 1;
} else {
if(x[i] == leader) c++;
else c--;
}
}
if(c == 0) return NULL;
else {
c = 0;
for(i=0; i<n; i++){
if(x[i] == leader) c++;
}
if(c > n/2) return leader;
else return NULL;
}
}
Я не являюсь автором этого код, но это будет работать для вашей проблемы. Первая часть ищет потенциального лидера, вторая проверяет, появляется ли он в массиве более n / 2 раз.
Найти медиану, она занимает O (n) в несортированном массиве. Поскольку более n / 2 элементов равны одному значению, медиана также равна этому значению.
Ну, вы можете выполнить радикальную сортировку по месту, как описано здесь [pdf] , это не требует дополнительных затрат. пространство и линейное время. затем вы можете сделать один проход, считая последовательные элементы и заканчивая счетом> n / 2.
Моей первой мыслью (недостаточно) было бы:
- Сортировать массив на месте
- Вернуть средний элемент
Но это будет O (n log n), как и любое рекурсивное решение.
Если вы можете деструктивно модифицировать массив (и применяются различные другие условия), вы можете выполнить проход, заменив элементы их счетчиками или что-то. Знаете ли вы что-нибудь еще о массиве и можете ли вы его изменить?
Редактировать Оставив здесь мой ответ для потомков, но я думаю, что у Скита он есть.
Как насчет: случайным образом выберите небольшое подмножество из K элементов и найдите дубликаты (например, первые 4, первые 8 и т. д.). Если K == 4, то вероятность не получить как минимум 2 дубликата составляет 1/8. если K == 8, то оно становится менее 1%. Если вы не нашли дубликатов, повторите процедуру, пока не сделаете. (Предполагая, что другие элементы распределены более случайным образом, это будет работать очень плохо, скажем, с 49% массива = "A", 51% массива = "B").
Например:
findDuplicateCandidate:
select a fixed size subset.
return the most common element in that subset
if there is no element with more than 1 occurrence repeat.
if there is more than 1 element with more than 1 occurrence call findDuplicate and choose the element the 2 calls have in common
Это операция постоянного порядка (если набор данных не плохой), поэтому выполните линейное сканирование массива, чтобы (N) проверить.
This is what I thought initially.
I made an attempt to keep the invariant "one element appears more than n/2 times", while reducing the problem set.
Lets start comparing a[i], a[i+1]. If they're equal we compare a[i+i], a[i+2]. If not, we remove both a[i], a[i+1] from the array. We repeat this until i>=(current size)/2. At this point we'll have 'THE' element occupying the first (current size)/2 positions. This would maintain the invariant.
The only caveat is that we assume that the array is in a linked list [for it to give a O(n) complexity.]
What say folks?
-bhupi