Dominanta ze 100 elementowej tablicy

Witajcie. Mam już posortowaną 100 elementową tablicę , do której losowane są liczby z zakresu 1-10. Jak wskazuje nazwa tematu, mam znaleźć liczbę, która wystepuje najczęściej. No i niby wiem jak to zrobić, ale sposób ten jest bardzo prymitywny. Można przechodzić po wszystkich elementach tablicy i zwiększał licznik dopóki tab[i] < tab[i+1] . No ale wtedy trzeba byłoby zrobić 10 takich liczników, i na tym polega prymitywizm tej "mojej metody" :D Macie jakieś inne pomysły na zminimalizowanie i zoptymalizowanie rozwiązania tego problemu? Pozdrawiam!

Sortujesz i wybierasz tę, która występuje najczęściej. Masz wtedy tylko 2 zmienne.

dla dziesięciu tysięcy rekordów to ja bym się nie wysilał - może to odpowiedź jakaś jest...

One już są posortowane, teraz chodzi o to w jaki sposób je porównać. Winefresh, właśnie chodzi mi o to jak wybrać i znaleźć tę która występuje najczęściej.

W C#, bo mam wstręt do C++, myślę, że połapiesz się jaka jest myśl przewodnia:

var random = new Random((int)DateTime.Now.Ticks);
var histogram = new byte[10];
var data = Enumerable.Repeat(0, 10000).Select(r => random.Next(1, 10)).ToArray();

foreach (var d in data) ++histogram[d - 1]; // korzystam z przyjemnej właściwości danych wejściowych do zliczenia ile jest których

var max = histogram.Select((count, index) => new { Count = count, Index = index}).OrderByDescending(el => el.Count).First().Index + 1;

Edit: jeśli są posortowane, to możesz to zrobić jeszcze szybciej - dla każdej z liczb metodą bisekcji wyszukujesz prawego sąsiada, wiedząc gdzie sąsiad się zaczyna masz ilość wystąpień danej liczby, potem powtarzasz to dla prawego sąsiada i tak aż do końca. Złożoność obliczeniowa to O(n*log2(m)), m - ilość danych, n - ilość różnych liczb. Złożoność obliczeniowa mojego kodu jest dużo wyższa dla m >> n - O(m).

Ciężko mi się w tym połapać... No nic, pozostała chyba opcja prymitywna, bo na inną nie mam pomysłu, a właściwie po prostu nie wiem jak ją wykonać.

Możesz też zrobić tak:

int tab[] = {1, 2, 3, 4, 4, 4, 4, 7, 7, 7};
int actual = tab[0];
int amount = 1;
int maxAmount = 1;
int elem = tab[0];
int size = 10;

for (int i = 1; i < size; i++) {
	if (tab[i] == actual) {
		amount++;
	} else {
		if (amount > maxAmount) {
			elem = actual;
			maxAmount = amount;
		}
		actual = tab[i];
		amount = 1;
	}
}
if (amount > maxAmount) {
	elem = actual;
	maxAmount = amount;
}

printf("%d\t%d", elem, maxAmount);

@mistergol: co w tym takiego skomplikowanego? Nie wiesz co to histogram, to idziesz sobie na wikipedię i czytasz, aż zrozumiesz. Wiedząc, co to histogram patrzysz jeszcze raz na kod. Rozbijasz go na prostsze przypadki, np. tablica pięciu elementów o trzech wartościach, i patrzysz co się dzieje.

Zobacz:
data | histogram | index(max)
1, 2, 4, 4 | 1, 1, 0, 2 | 4
1, 1, 1, 4 | 3, 0, 0, 1 | 1
1, 2, 2, 5, 1, 4 | 2, 2, 0, 1, 1 | niezdefiniowany - 1 albo 2

itp. Data to dane wejściowe z przedziału 1..n. Histogram to liczba wystąpień poszczególnych liczb, na pozycji 1 liczba wystąpień jedynki, na pozycji trzeciej liczba trójek itp (a ponieważ tablice w C++ oraz C# indeksuje się od zera, to żonglowanie jedynką - raz odjąć, a raz dodać). Index(max) to indeks maksymalnej pozycji w histogramie.

Rozwiązanie o złożoności O(m*log(n)), gdzie n - ilość danych, m - ilość różnych liczb, ponownie w C#

		private static int FindIndexOfRightNeighbour(int me, int start, int[] everybody)
		{
			int l = start, len = everybody.Length - 1, r = len;

			if (everybody[len] <= me)
				return len + 1;
			if (everybody[0] > me)
				return 0;

			while (l <= r)
			{
				int m = (l + r) >> 1;
				int x = everybody[m];

				if (everybody[m + 1] > me && x == me)
					return m+1;

				if (x <= me)
					 l = m + 1;
				  else
					 r = m - 1;
			}
			
			throw new Exception();
		}


		var random = new Random((int)DateTime.Now.Ticks);
		var data = Enumerable.Repeat(0, 500).Select(rnd => random.Next(1, 14)).OrderBy(v => v).ToArray();

		int l = 0, r = 0, max = 0, value = 0, currentValue = data[0];
		while (true)
		{
			l = r;
			if (data[r + 1] != currentValue)
				++r; // tu drobna optymalizacja dla tablic z m >> n
			else
				r = FindIndexOfRightNeighbour(currentValue, r, data);
			if (r - l > max)
			{
				max = r - l;
				value = data[r-1];
			}

			if (r >= data.Length)
				break;
			currentValue = data[r];
		}

Wartość występująca najczęściej znajdzie się w zmiennej value. Jeśli kilka wartości występuje równie często, zwrócona zostanie najniższa. Można podciągnąć średnią złożoność obliczeniową do O(m*log(log(n)) stosując zmodyfikowany algorytm wyszukiwania binarnego, ale to już zostawię autorowi wątku.