Dominant number in array

[evaaa]

Hi all!

I am trying to find the dominant element of an array. My idea is to scan the original array and put every individual element in another array. If there is already the element I increase a counter. When counter>Array.length/2 then it is the dominant.
This should work with any array.

my effort so far
function mainFunc() {
var result = 0;
var myArray=[4,5,6,4,2,4,5,6,7];
//result = test(myArray);
//alert("{ " + myArray + " } --> " + result);
}

function test(A) {

var tempArray = new Array;

for(var i=0;i<A.length;i++){
// 1. check if A[i] exists in tempArray
for(var j=0;j<tempArray.length;j++){
if(A[i]==tempArray[j])
{

}

}

// 2. If A[i] exists, increase counter
if(A[i]!=tempArray[])

// 3. Check if counter > A.length/2
// 4. Return A[i]

// 5. If not, add A[i] to tempArray and set counter=1
//


}

return -1;
}

I can't find a way to make the second array correctly to extract the element with the correct counter.
Any ideas?

[donna1]

by dominant do you mean most common, like the Mode in maths?

The most common still might not necessarily be > half the elements.

like in 2,3,4,2,3,4,2,1
number 2 is the most common but still 3 instances are not as much as 4 which is half the array length

[evaaa]

Yes exactly. I mean more times than the half

[donna1]

Yes but the most common number may not be as common as half of them.
This is my effort and it finds the Mode


var i,j=0,finds=0,found;
var array = [1,4,2,3,4,1,4,2,4,4];
var temparray = new Array();
var counter = new Array();


function mode(){
for(i in array){
found=false;
for(j in temparray){
if(temparray[j]==array[i]){
counter[j]++;
found=true;}
}
if(found==false){
// if array[i] not found in temparray add it and increment the number of finds
temparray[finds]=array[i];
counter[finds]=1;
finds++;}
}
alert("variants found "+finds);

}

mode();
var highestIndex=0;
for(j=0;j<finds;j++){
if(counter[j]>=counter[highestIndex]){
highestIndex=j;}
}

alert("The Mode was"+temparray[highestIndex]);

[felgall]

See http://javascriptexample.net/extobjects83.php for code to find the mode that returns the value in an array (in case two or more numbers all occur the same number of times and more than any other number)

[007julien]

I propose this two lines script with a backreference regular expression

<script type="text/javascript">
//array to test
var arr=[1,41,222,33,40,18,22,41,2,2,41,42,27,41,58];

var lgt=0,nmb='',str=arr.sort().join(',').replace(/(,\d+)(\1+)/g,
	function(a,b){var m;if (lgt<(m=a.length/b.length)) {lgt=m;nmb=b.substr(1)}});
alert('This number '+nmb+' appaers '+lgt+' times');	

</script>

[donna1]

Originally Posted by 007julien

var lgt=0,nmb='',str=arr.sort().join(',').replace(/(,\d+)(\1+)/g,
function(a,b){var m;if (lgt<(m=a.length/b.length)) {lgt=m;nmb=b.substr(1)}});
alert('This number '+nmb+' appaers '+lgt+' times');

</script>[/CODE]

That is very clever Monsieur J, how does that work? In particular what does the replace / , \d \1 lot do? Not sure what backslashes do there?

[Old Pedant]

Well, (,\d) means "find a comma followed y one or more digits."

So it will match ",2" or ",41".

The (\1+) means "find the same thing matched by (,\d) one or more times.

So if you have ",2,2,2" that expression will first find ",2" and then see that there are two more occurrences of ",2" and end up matching all of ",2,2,2".

The only flaw in this code is that if NO string is found more than once, it will report back with [b[This number appaers 0 times[/b] (of course, the word should be "appears").

It also doesn't fulfill the requirement that the number be found more than half the time, but that's easy to do in a separate test.

[007julien]

An alert(arr.sort().join(',')) give the string 1,18,2,2,22,222,27,33,40,41,41,41,41,42,58 which is an alphanumeric sort (sort(function(a,b){return a-b}) will assume a numeric increasing sort).

The \1+ after the first sub-pattern (,\d+) in the regular expression /(,\d+)(\1+)/g is a back-reference (1 for first sub-pattern) which allows to match all repeated set of one comma followed by one or more digits.

Then the anonymous function is called only for the duplicated numbers

function(a,b){var m;if (lgt<(m=a.length/b.length)) {lgt=m;nmb=b.substr(1)}}

The first argument a is the matched pattern (for example ,2,2 and b the first sub-pattern (the first curly bracket : ,2 in this case). The count of repetitions is also a.length/b.length, we do not use the replace function (See this page for further explanations) but define lgt (for lengthsQuotient) and nmb (for one «dominant» number).

NB : Its easy to define lgt=1 and nmb=arr[0] (with a nmb=+b.substr(1) to store a number) to replace a «This number appaers 0 times» by a better «This number 1 appears 1 time» with an alert('This number '+nmb+' appears '+lgt+' time'+(1<lgt?'s':'');
It is also possible to define the half-length of the array and test only the larger values.

This script can certainly be improved. Especially, with a (,[^,]+) instead of (,\d+) to work with all kind of comma separated values to find duplicates elements...

Apologies English is not my mother tongue

[Old Pedant]

WHOOPS! I am wrong! And that code is fatally flawed!

Change the array to

var arr=[1,41,222,33,40,18,22,41,2,2,42,27,58];

and it gives the answer

This number 2 appears 3 times

Reason: After sorting the array and converting it to a string, you get:

1,18,2,2,22,222,27,33,40,41,41,42,58

And, as I mentioned, when it sees ",2" it looks for repetitions and indeed FALSELY finds 3:

1,18,2,2,22,222,27,33,40,41,41,42,58

Okay...here's a small challenge: Fix that code!

HINT: The fix is nearly trivial.

[Old Pedant]

Though the code is flawed in another way: If there are two sets of numbers with the same count, it only finds the first such. This, too, could be fixed.

[Old Pedant]

W.T.H. This was fun.

My version that fixes both flaws. Not as compact, but easier to understand, I hope:

<script type="text/javascript">
function zonk(a,b)
{
    var m = a.length / b.length;
    if (lgt <= m ) 
    {
        if ( lgt < m ) { nmb = [ ]; }
        lgt = m;
        nmb.push( b.replace(/,/g,"") );
    } 
}

//array to test
var arr=[1,41,222,33,40,18,22,41,2,2,42,27,58];

document.write('<hr/>In the array<br/>[' + arr + ']<br/>');

var lgt = 0;
var nmb = [ ];
var str = arr.sort();
str = "," + str.join(',,') + ","
str.replace( /(,\d+,)(\1+)/g, zonk );

document.write('the number(s) ' + nmb.join(" and ") + ' appear(s) '+lgt+' times<hr/>');	
</script>

[evaaa]

Than you all,

I tried a bit harder. That's my code


function mainFunc() {
var result = 0;
var myArray=[2,4,3,3,3,5,3,5,3,3];
result = test(myArray);
alert("{ " + myArray + " } --> " + result);
}

function test(A) {

var tempArray = new Array;

for(var i=0;i<A.length;i++){
var index = -1;

// 1. check if A[i] exists in tempArray
for(var j=0;j<tempArray.length;j++){

if(A[i]==tempArray[j][0])
{
index = j;
}
}

if(index == -1)
{
tempArray.push(A[i]);
tempArray[tempArray.length-1][1] = 1;
}
else
{
tempArray[index][1]++;
if(tempArray[index][1] > A.length/2)
{
return tempArray[index][1];
}
}


}

return -1;
}

The problem is that tempArray can't get the second dimension.
I need it to be:

tempArray[[4,1],[2,1],[3,2],[5,5]....]
and when the second element of one sub-array is bigger than A.length/2 to return this element.

[007julien]

A shorter script with Old Pedant observations

var arr=[1,41,222,33,41,41,41,40,41,18,41,41,41,22,41,2,2,41,42,27,41,58];

var dominant=null,halfLength=arr.length/2,str=arr.sort().join(',').replace(/(,\d+)(\1+)(?=,)/g,
	function(a,b){if (halfLength<=a.length/b.length) {dominant=+b.substr(1)}});

var msg=dominant?'Dominant number : '+dominant:'No dominant number !'
alert(msg);

EDIT : A new corrections repetition followed by a comma or a word boundary. An assertion like (\1+)(?=,|\b) matches a repetition followed by a comma or a word boundary, but does not include the comma in the match. There is never two dominant numbers !

[Old Pedant]

Is *THIS* what you are after:

<script type="text/javascript">

function findMode( arr )
{
    var counts = [ ];
    for ( var a = 0; a < arr.length; ++a )
    {
        var elem = "E" + arr[a];
        if ( counts[ elem ] == null ) 
        {
            counts[ elem ] = 1;
        } else {
            ++counts[ elem ];
        }
    }
    var half = 0.5 * arr.length;
    for ( var elem in counts )
    {
        // I don't think >= half works...what if the array is simply [1,2] ?? SO I used >
        if ( counts[elem] > half ) { return elem.substring(1); }
    }
    return "NONE";
}

var atest = [ 1, 37, 3, 2, 44, 1, 99, 1 ];
document.write( "Mode of [" + atest + "] is " + findMode(atest) + "<hr>" );

atest = [ 77, 101, 191, 91, 91, 191, 191, 191, 191 ];
document.write( "Mode of [" + atest + "] is " + findMode(atest) + "<hr>" );
</script>