Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitea94f34

Browse files
authored
Merge pull requestalgorithm-visualizer#202 from archie94/majority-vote-problem
Majority Vote Problem
2 parents17b0a94 +3de3211 commitea94f34

File tree

4 files changed

+83
-1
lines changed

4 files changed

+83
-1
lines changed

‎algorithm/category.json‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -46,7 +46,8 @@
4646
},
4747
"greedy": {
4848
"list": {
49-
"job_scheduling":"Job Scheduling Problem"
49+
"job_scheduling":"Job Scheduling Problem",
50+
"majority_element":"Majority Element(Boyer–Moore majority vote algorithm)"
5051
},
5152
"name":"Greedy"
5253
},
Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
functionisMajorityElement(element){
2+
varcount=0;
3+
logger._print('Verify majority element '+element);
4+
for(vari=N-1;i>=0;i--){
5+
tracer._notify(i,A[i])._wait();
6+
if(A[i]==element){
7+
count++;
8+
}else{
9+
tracer._denotify(i);
10+
}
11+
}
12+
logger._print('Count of our assumed majority element '+count);
13+
if(count>Math.floor(N/2)){
14+
logger._print('Our assumption was correct!');
15+
returntrue;
16+
}
17+
logger._print('Our assumption was incorrect!');
18+
returnfalse;
19+
}
20+
21+
functionfindProbableElement(){
22+
varindex=0,count=1;
23+
tracer._select(index)._wait();
24+
logger._print('Beginning with assumed majority element : '+A[index]+' count : '+count);
25+
logger._print('--------------------------------------------------------');
26+
for(vari=1;i<N;i++){
27+
tracer._notify(i,A[i])._wait();
28+
if(A[index]==A[i]){
29+
count++;
30+
logger._print('Same as assumed majority element! Count : '+count);
31+
}else{
32+
count--;
33+
logger._print('Not same as assumed majority element! Count : '+count);
34+
}
35+
36+
if(count===0){
37+
logger._print('Wrong assumption in majority element');
38+
tracer._deselect(index);
39+
tracer._denotify(i);
40+
index=i;
41+
count=1;
42+
tracer._select(i)._wait();
43+
logger._print('New assumed majority element!'+A[i]+' Count : '+count);
44+
logger._print('--------------------------------------------------------');
45+
}else{
46+
tracer._denotify(i);
47+
}
48+
}
49+
logger._print('Finally assumed majority element '+A[index]);
50+
logger._print('--------------------------------------------------------');
51+
returnA[index];
52+
}
53+
54+
functionfindMajorityElement(){
55+
varelement=findProbableElement();
56+
if(isMajorityElement(element)===true){
57+
logger._print('Majority element is '+element);
58+
}else{
59+
logger._print('No majority element');
60+
}
61+
}
62+
63+
findMajorityElement();
Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
varA=[1,3,3,2,1,1,1];
2+
varN=A.length;
3+
4+
vartracer=newArray1DTracer('List of element')._setData(A);
5+
varlogger=newLogTracer('Console');
Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
{
2+
"Majority Element(Boyer–Moore majority vote algorithm)":"The majority vote problem is to determine in any given sequence of choices whether there is a choice with more occurrences than half of the total number of choices in the sequence and if so, to determine this choice.",
3+
"Complexity": {
4+
"time":" O(N)",
5+
"space":"O(logN)"
6+
},
7+
"References": [
8+
"<a href='https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm'>Wikipedia</a>"
9+
],
10+
"files": {
11+
"basic":"Find majority element in array using Boyer–Moore majority vote algorithm"
12+
}
13+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp