мажорирующий элемент

[kyCa4ka]

привет всем. помогите пожалуйста кто может с задачкой. буду рад любой помощи..

Мажорирующим элементом в массиве A[1..N] будем называть элемент, встречающийся в массиве более N/2 раз. Легко заметить, что в массиве может быть не более одного мажорирующего элемента. Например, мас-сив 3, 3. 4, 2, 4, 4, 2, 4, 4 имеет мажорирующий элемент 4, тогда как в массиве 3, 3, 4, 2, 4, 4, 2, 4 мажорирующего элемента нет. Необходимо определить, есть ли в массиве мажорирующий элемент, и если есть, то какой.

зы. в ответ предлагаю помощь по веб-дизайну.

 

[LAW]

Ты алгоритм-то сего действа представляешь?

 

[Dmirys]

Ну а, например, так:
1. Отсортировать массив
2. Выполнить примерно следующую схему:

int arr[] = {1, 1, 1, 5, 5, 5, 5, 5, 5, 5, 5, 5, 7, 8, 9, 9};

for (int i = 0, count = 1; i < sizeof(arr) - 1; i++) {
if (arr[i] == arr[i + 1]) {
if (++count > sizeof(arr) / (2 * sizeof(int))) {
// Здесь вывод сообщения, что элемент найден и равен arr[i]
break;
}

continue;
} else {
count = 1;
}

}

Поиск мажорирующего элемента имеет смысл для массива минимум из трех элементов.

 

[Kmet]

Для: Dmirys
От задачек такого родa обычно требуется сложность О(N)

мне почему то казалось что sizeof возвращает размер в байтах

 

[kyCa4ka]

<!--QuoteBegin-Kmet+17:11:2006, 10:49 -->
<span class="vbquote">(Kmet @ 17:11:2006, 10:49 )</span><!--QuoteEBegin-->От задачек такого родa обычно требуется сложность О(N)

[snapback]48080" rel="nofollow" target="_blank[/snapback]​

[/quote]
если так всё просто то помогите а млин осталось только эта последняя задачка вот у мя есть исходник на паскале:

for i:=1 to N-1 do
for j:=2 to N do
if A>A[j]
then
begin
tmp:=A;
A:=A[j];
A[j]:=tmp
end;
Count:=1; { Количество одинаковых элементов }
for i:=2 to N do
if A<>A[i-1]
then if Count > N div 2
then
begin
writeln('Mажорирующий элемент ',A[i-1]); { Распечатать } Halt { Стоп }
end;
else Count:=0 { Начать подсчет для следующего элемента}
else Count:=Count+1; { Увеличить счетчик для текущего элемента }

 

[Kmet]

Кто сказал что просто? В общем случае все как раз наоборот. Все зависит от диапазона элемнентов которые могут встретиться в массиве. И для общего случае скореее всего потребуется написание каго-нибудь хитрого хеш словаря с поддержкой колизий.=)

Если диапон ограничен тогда действительно не сложно=)
Создаем массив который будет хранить сколько раз элемент встречался,и индексируем его(этот массив) самим же элементом. Таким образом можно обойтись без сортироки

 

[ZZmiy]

Кто сказал что просто? В общем случае все как раз наоборот. Все зависит от диапазона элемнентов которые могут встретиться в массиве. И для общего случае скореее всего потребуется написание каго-нибудь хитрого хеш словаря с поддержкой колизий.=)

можно, наример, std::map<int,int> - чем плох?

 

[European]

Судя по примеру на Паскале, на сложность O(N) можно забить

 

[Kmet]

можно, наример, std::map<int,int> - чем плох?

Я говорил о хитром хеш словаре с подержкой коллизий
std::map и не хитрый и не хеш и коллизии тоже естестно не обробатывает. Хотя конечно на числовом ряду проку от хештрование не будет, это так для общности.

Из stl можно взять std::multimap или hash_map, но этот контейнер еще не вошел в стандарт

 

[kyCa4ka]

так может кто исходником помочь или нет? :huh: или хотяб частично

 

[zugr]

Вот примерный алгоритм (JavaScript):

function Major(arr)
{
var ss=new Object();
var n=arr.length;
for(var i in arr) {
var v=arr[i];
if (ss[v]==null) {
ss[v]=Math.round(n/2);
} else if ( i <= ss[v] ) {
if (n==++ss[v])
return v;
}
}
return null;
}

arr=new Array(1,2,3,4,9,1,1,1,1,5);
var rez=Major(arr);
if (null==rez)
print("Array not have major");
else
print("Major element is "+rez);

здесь ss - и есть map счётчиков, только мажорный элемент может довести его до N.
Почему считаем до N:
1. Это позволит закончить поиск мажорного элемента до завершения просмотра всего массива;
2. Это позволяет игнорировать элементы, которые уже не станут мажорными даже если все оставшиеся непросмотренные будут такимиже.

Сложность алгоритма в худшем случае O(N*log(N))

Думаю на Си перевести можно

 

[kyCa4ka]

а если JavaScript незнаю

 

[zugr]

а если JavaScript незнаю

Это плохо, но и не страшно
Начинай переводить на Си с того что понимаешь, пиши если что не выходит, помогут

 

[kyCa4ka]

int array[N];

добрые люди пожалуйста помогите с сортировкой на этом этапе далее вроде всё правильно..

int count =0, i =0;
int maz_el;

//
while( i < N-1 ){
maz_el = array[i];
if( array[i] == array [i+1] )
count++;
else
if( count>N/2 ){
//есть маж. эл. maz_el;
else
count = 0;
}
i++;
}

 

[kyCa4ka]

помогите пожалуйста кто нибудь дописать алгоритм

 

[zugr]

помогите пожалуйста кто нибудь дописать алгоритм

Всё просто:

#include <iostream>
#include <vecotr>
#include <map>

typedef int el;
typedef std::vector<el> Array;
typedef std::map<el,int> Object;

//function Major(arr)
el* Major(Array& arr)
//{
{
//var ss=new Object();
Object ss;
//var n=arr.length;
int n=arr.size();
//for(var i in arr) {
for(int i=0; i!=arr.size(); i++) {
//var v=arr[i];
el v=arr[i];
//if (ss[v]==null) {
if ( ss.find(v) == ss.end() ) {
// ss[v]=Math.round(n/2);
ss.insert(Object::value_type(v,int(n/2)));
//} else if ( i <= ss[v] ) {
} else if ( i <= ss.find(v).second ) {
//if (n==++ss[v])
if (n == ++(ss.find(v).second) )
//return v;
return arr+i; // не v, т.к. функция возвращает указатель на элемент масива
//}
}
//}
}
//return null;
return null;
//}
}


void main(void)
{
// arr=new Array(1,2,3,4,9,1,1,1,1,5);
el _arr[]={1,2,3,4,9,1,1,1,1,5}
Array arr(_arr,_arr+sizeof(_arr)/sizeof(el));
// var rez=Major(arr);
el* rez = Major(arr);
//if (null==rez)
if (null == rez)
//print("Array not have major");
std::cout << "Array not have major" << std::endl;
//else
else
//print("Major element is "+rez);
std::cout << "Major element is " << *rez << std::endl;
}

Но я не отлаживал, так что баги шукай, наверняка есть.