Trivial `O(n^2)`

solution:

```
for (int i = 0; i < nums.length; ++i) {
int count = 0;
for (int j = i; j < nums.length; ++j) {
if (nums[i] == nums[j]) {
count++;
}
if (count > nums.length / 2) return nums[i];
}
}
```

This is filtered by a test case that times out: `[24999*1, 25001*2]`

, it runs for more than 1 second.

A simple modification to this algorithm which skips the continous `1`

s passes all test cases:

```
for (int i = 0; i < nums.length; ++i) {
int count = 0;
int continuous = 0;
boolean mismatch = false;
for (int j = i; j < nums.length; ++j) {
if (nums[i] == nums[j]) {
if (!mismatch) continuous++;
count++;
} else {
mismatch = true;
}
if (count > nums.length / 2) return nums[i];
}
i += continuous; // skip elements that will not be majority for sure
--i; // because the next loop starts by incrementing
}
```

I propose to add a new test case which looks like this:

```
final int n = 50000; // counts will be {1=12500, 2=12499, 3=25001}
int[] nums = new int[n];
for (int i = 0; i < n / 2; ++i) {
nums[i] = i % 2 + 1;
}
for (int i = n / 2 - 1; i < n; ++i) { // - 1 to have 1 more 3s than 1s and 2s
nums[i] = 3;
}
```

This will make the modified algorithm choke with ~900 ms runtime.