Timeline for Divide and Conquer majority element algorithm
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 3, 2017 at 18:31 | comment | added | xavierm02 | I finally managed to make it give a "really" wrong answer: $[0,1,1,1, 0,1,1,1, 0,1,1,1, 0,1,1,1, 2,2,2,2, 2,2,2,2, 2,2,2,3, 4,5,6,7]$ return $[2,10]$ even though $1$ appears $12$ times while $2$ only appears $11$ times. The idea is that $0,1,1,1$ makes it count $1$ only twice while it's there $3$ time and $1,1,1,1$ makes it count it $4$ times and it's really here $4$ times. So you just have to make the difference between the estimate and the real value big enough to have space for another number to have some number of occurrences in between. | |
| Mar 3, 2017 at 18:20 | comment | added | xavierm02 | On $[0,1,1,0]$, it returns $[None, 1]$. | |
| Mar 3, 2017 at 18:18 | history | edited | Jack Black | CC BY-SA 3.0 |
added 88 characters in body
|
| Mar 3, 2017 at 18:11 | comment | added | xavierm02 | I depends on what you call working. It fails to return the correct number of occurrences and my feeling is this I should be able to use this in a bigger array to make it fail to find the correct element. | |
| Mar 3, 2017 at 18:06 | comment | added | Jack Black | @xavierm02 It works too. My intuition is if it works for [0,1,0,1,0,1...,0] then it should work for all test cases. | |
| Mar 3, 2017 at 18:04 | history | edited | Jack Black | CC BY-SA 3.0 |
deleted 39 characters in body
|
| Mar 3, 2017 at 17:59 | comment | added | skankhunt42 | If you're looking for a linear time algorithm, try this en.wikipedia.org/wiki/… | |
| Mar 3, 2017 at 17:54 | answer | added | quicksort | timeline score: 2 | |
| Mar 3, 2017 at 17:48 | comment | added | Jack Black | @xavierm02 It works in this case. | |
| Mar 3, 2017 at 17:46 | comment | added | xavierm02 | How about $[0;1;1;1]$? | |
| Mar 3, 2017 at 17:44 | comment | added | Jack Black | @xavierm02 There is still no majority, there needs to be an element with 5 or more occurrences | |
| Mar 3, 2017 at 17:40 | comment | added | Jack Black | @xavierm02 But in this case there is no majority, there needs to be more than $n/2$ occurrences | |
| Mar 3, 2017 at 17:26 | history | asked | Jack Black | CC BY-SA 3.0 |