Finne hvilken heltallsverdi i en tabell som finnes flest ganger

[mske]

Hei!

 

Lurer litt på en liten sak.

Ønsker å loope gjennom en tabell og finne hvilket element som oppstår flest ganger. La oss si jeg har følgende tabell:

 

int[] tab = {2, 3, 7, 5, 2, 3, 2, 9, 8};

 

Da vil jeg få følgende svar: "Tallet som forekommer flest ganger er: 2. Det forekommer 3 ganger. "

 

Sliter litt med å omsette det i kode. Tenker noe slikt:

 

public static void finnesFlestAv(int[] tab) {

   for(int i=0; i<tab.length; i++) {
       //Bør jeg lage en hjelpetabell for å holde styr på hvor mange ganger hvert tall        forekommer?
   }
}

[torbjørn marø]

Antar at dette kanskje ikke hjelper deg, men her er en LINQ-løsning i C# (en gang i tiden så C# ganske likt ut som Java (: )

 

int[] tab = { 2, 3, 7, 5, 2, 3, 2, 9, 8 };

var answer = tab
   .GroupBy(x => x)
   .Select(group => new { Value = group.Key, Count = group.Count() })
   .OrderByDescending(x => x.Count)
   .First();

Console.WriteLine("{0}. Det forekommer {1} ganger", 
   answer.Value, answer.Count);

[fleskesvor]

int[] tab = {2, 3, 7, 5, 2, 3, 2, 9, 8};
Map<Integer, Integer> tabCount = new HashMap<Integer, Integer>();

for (int t : tab)
   tabCount.put(t, tabCount.containsKey(t) ? tabCount.get(t) + 1 : 1);

int max = 0, value;

for (Integer v : tabCount.keySet()) {
   int num = tabCount.get(v);
   if (num > max) {
       max = num;
       value = v;
   }
}

[torbjørn marø]

En unødvenig linje i besvarelsen min Korreksjon:

 

int[] tab = { 2, 3, 7, 5, 2, 3, 2, 9, 8 };

var answer = tab
   .GroupBy(x => x)
   .OrderByDescending(x => x.Count())
   .First();

Console.WriteLine("{0}. Det forekommer {1} ganger", 
   answer.Key, answer.Count());

 

Fleskesvors svar er nok derimot akkurat hva du er ute etter, og anvendelig i de fleste imperative språk. Min løsning er mere typisk for funksjonell, stream-basert programmering.

Endret 25. oktober 2011 av torbjørn marø

[Kiff]

Med Collections.frequency(...) slipper du å telle selv

 

	Integer[] tab = { 2, 3, 7, 5, 2, 3, 2, 9, 8 };
	List<Integer> l = Arrays.asList(tab);

	int max = 0, value = 0;
	for (Integer val : l) { //Edit: evt bytt l med "new HashSet<Integer>(l)" for å loope unike entries 
		int frequency = Collections.frequency(l, val);
		if (frequency > max) {
			max = frequency;
			value = val;
		}
	}

	System.out.println(value + "," + max);

Endret 25. oktober 2011 av Kiff

[fleskesvor]

En typisk perl-implementasjon som bonus:

 

map$h{++$a[$_]}=$_,(2,3,7,5,2,3,2,9,8);
$d=(sort{$b-$a}@a)[0];
print"$d forekomster av tallet $h{$d}\n"

Endret 25. oktober 2011 av fleskesvor

[hlnd]

Uten noe innebygd:

 

// Sortering, en iterasjon, kjøretid O(NlogN + N) = O(NlogN)
// Vil vel egentlig anta at .sort optimaliserer for heltall, så med radix eller bucket sort er det vel mulig å få det enda bedre.
// Hashing / hashmap som nevnt tidligere her kan vel få til i lineær kjøretid ved å lagre antall av hver verdi i et hashmap, finne største verdi og tilsvarende nøkkel.
{
int[] tab = { 2, 3, 7, 5, 2, 3, 2, 9, 8, 4, 5, 6, 4, 2, 8, 3 };
Arrays.sort(tab);
int maxfreq = 0;
int maxval = 0;
Integer value = null;
int count = 0;

for (int i = 0; i < tab.length; i++) {
	if (value != null && tab[i] == value) {
		count++;
	} else {
		if (count > maxfreq) {
			maxfreq = count;
			maxval = tab[i-1];
		}

		value = tab[i];
		count = 1;
	}
}

System.out.println("Max: " + maxval + ", freq: " + maxfreq);


}

{
// Mindre kode, to løkker, kjøretid O(n^2)
int[] tab = { 2, 3, 7, 5, 2, 3, 2, 9, 8, 4, 5, 6, 4, 2, 8, 3 };
int maxfreq = 0;
int maxval = 0;
for (int i = 0; i < tab.length; i++) {
	int count = 0;
	for (int j = 0; j < tab.length; j++) {
		if (tab[i] == tab[j])	count++;
	}
	if (count > maxfreq) {
		maxfreq = count;
		maxval = tab[i];
	}
}

System.out.println("Max: " + maxval + ", freq: " + maxfreq);
}

Endret 27. oktober 2011 av hlnd

[Matsemann]

		int[] tab = {2, 3, 7, 5, 2, 3, 2, 9, 8};		
	int[] count = new int[20];		
	for(int number: tab) {
		count[number]++;
	}		
	for(int i = 0; i < count.length; i++) {
		System.out.println("Tallet " + i + " forekommer " + count[i] + " ganger");
	}

Sånn veldig enkelt om det er lite spenn i verdiene. count sin lengde må være lenger enn høyeste tallet i tab. Man kan evt. loope over tab en gang først og finne høyeste element.

Ikke veldig elegant, men liten og lett å forstå. O(n) kjøretid siden han over påpekte sin..

[hlnd]

Er vel strengt tatt O(n+k) dersom du lar k være antatt maksgrense.

 

HashMap<Integer, Integer> freq = new HashMap<>();
int[] tab = { 2, 3, 7, 5, 2, 3, 2, 9, 8, 4, 5, 6, 4, 2, 8, 3 };

int maxfreq = 1;
int number = 0;

for (int val : tab){
if (!freq.containsKey(val))
	freq.put(val, 1);
else {
	int newfreq = freq.get(val) + 1;
	freq.put(val, newfreq);

	if (newfreq > maxfreq){
		maxfreq = newfreq;
		number = val;
	}
}
}

System.out.println("Max: " + number + ", freq: " + maxfreq);

 

... blir O(n), om jeg ikke tar helt feil. "Antar" at elementet som forekommer flest ganger vil forekomme >=2 ganger, velger ellers det første elementet, så vil stemme for alle tabeller av int med størrelse >= 1.

[srbz]

Pirk - du må også ha en generisk konstruktør:

HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>();

 

 

Denne måten å gjøre det på gjør faktisk også det som spesifiseres i førstepost. Matsemann sin løsning skriver kort og greit ut alle counts fra 0 til 19, men man må fremdeles selv finne ut hvilken som opptrer flest ganger. Forsåvidt en enkel jobb, men det blir ekstra kode.

[torbjørn marø]

Er vel strengt tatt O(n+k) dersom du lar k være antatt maksgrense.

O(n+k) = O(n), altså lineær kompleksitet.

Endret 11. november 2011 av torbjørn marø

[Matsemann]

Ja, marø sier som jeg tenker.

 

Eksempelet mitt var mer et direkte svar til trådstarter, der han har begynt å lage en for løkke, og skriver

//Bør jeg lage en hjelpetabell for å holde styr på hvor mange ganger hvert tall forekommer?

og jeg da laget et eksempel på hvordan jeg ville gjort det.

[hlnd]

Er vel strengt tatt O(n+k) dersom du lar k være antatt maksgrense.

O(n+k) = O(n), altså lineær kompleksitet.

... når du antar at det høyeste tallet i tabellen ikke vil øke når problemkomplekseten øker. Tror ikke det er oppgitt i oppgaveteksten.

 

Er ikke så uvanlig å ha med nesten-konstantledd i O-notasjon, se f.eks. en.wikipedia.org/wiki/Radix_sort eller en.wikipedia.org/wiki/Counting_sort som Mats i praksis har gjort første del av. Kjøretid nettopp O(n+k)

 

@srbz: ja, så ikke den. Var nok litt for rask på ctrl+space. Men koden kompilerer og kjører.

Endret 13. november 2011 av hlnd

[torbjørn marø]

Er vel strengt tatt O(n+k) dersom du lar k være antatt maksgrense.

O(n+k) = O(n), altså lineær kompleksitet.

Er ikke så uvanlig å ha med nesten-konstantledd i O-notasjon, se f.eks. en.wikipedia.org/wiki/Radix_sort eller en.wikipedia.org/wiki/Counting_sort som Mats i praksis har gjort første del av. Kjøretid nettopp O(n+k)

Slik jeg lærte Big-O-notasjon på uiversitetet mener jeg å huske at det vil bli oppfattet som direkte feil å konkludere med at en algoritme har en kombleksitet av O(n + k). Da snakker man ikke lenger Big-O men en av de andre notasjonene for asymptotisk kompleksitet. Men jeg er ingen ekspert!

[GeirGrusom]

Slik jeg lærte Big-O-notasjon på uiversitetet mener jeg å huske at det vil bli oppfattet som direkte feil å konkludere med at en algoritme har en kombleksitet av O(n + k). Da snakker man ikke lenger Big-O men en av de andre notasjonene for asymptotisk kompleksitet. Men jeg er ingen ekspert!

På min skole var det litt delt. Under algoritme-faget så ble jeg fortalt akkurat dette, men under optimering fikk jeg høre at det var feil.

Men jeg tenker svaret ligger midt imellom: dersom forskjellen er vesentlig, så er kan det være viktig å påpeke dette.

Endret 14. november 2011 av GeirGrusom