Numbers that appear more than half of the time in the array

describe

Give a length of n Array of , There is a number in an array that appears more than half the length of the array , Please find out the number . For example, enter a length of 9 Array of [1,2,3,2,2,2,5,4,2]. Because of the number 2 Appears in the array 5 Time , More than half the length of the array , So output 2.

Data range ：n \le 50000n≤50000, The value of the element in the array  0 \le val \le 100000≤val≤10000

requirement ： Spatial complexity ：O(1), Time complexity  O(n)

Input description ： Ensure that the array input is not empty , And ensure that there is a solution

  Their thinking

        Subject requirements “ Spatial complexity ：O(1), Time complexity  O(n)”, Note that you cannot use data structures such as external arrays , And can only traverse the array once .

        There is a number in an array that appears more than half the length of the array , This is the key point of the topic . More than half of the numbers appear, which means that if two different numbers in the array are picked out separately , Then the rest is at least more than 1 A digital , This number must be the number we are looking for . Then how can we simulate picking up two different numbers in the process of traversing the array ？

        One plan I came up with is

        1、 Using variables target Mark as the value we are looking for , Initialize the value to the zeroth element of the array .

        2、 Then a variable is used to represent the position that has been traversed. After removing two different elements , The number of the same elements remaining .

        3、 From array No 2 Position to start traversing , If the currently traversed elements and target identical , Only let sameNum Add 1, Then go to the next cycle .

        4、 If the currently traversed subscript index Elements and target Different target values , At this time, judge sameNum reduce 1, And then determine sameNum Is the value equal to 0, If it is equal to 0 That means located in 0~index All numbers between meet two different . By this time target Set to current index The value of the subscript ,sameNum Revert to 1;

        5、 After traversing the array , Last target The saved value must be the number with more occurrences than the general length of the array .

Let's give you an example , Easy to understand ：

The array is ：array = [1,2,3,2,2,2,5,4,2] The target value is 2

The first set target=array[0], sameNum=1. From the subscript 1 To traverse the

1、 First traversal ,index = 1,2!=1, therefore sameNum = sameNum-1. When sameNum=0 At this time, you need to reset target=array[index], namely target=2, sameNum=1;

2、 Second traversal ,index =2, 3!=2, Operate as above . Last target=3, sameNum=1;

3、 The third traverse ,index =3,2!=3, Operate as above . Last target=2, sameNum=1;

4、 The fourth traversal ,index=4,2==2,sameNum=sameNum+1, Last sameNum=2;

5、 The fifth traversal ,2==2, ditto , Last sameNum=3;

6、 The seventh traversal ,5!=2,sameNum = sameNum-1, therefore sameNum=2, No reset target;

7、 The eighth traversal ,4!=2,sameNum = sameNum-1, therefore sameNum=1, No reset target;

8、 The ninth traversal ,2==2,sameNum = sameNum+1, therefore sameNum=2, No reset target;

9、 return target=2.

Post the code ：

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        // A number is more than half the length of the array , It means removing two different numbers , There must be some numbers left , And these numbers are the same 
        int target = array[0];
        int length = array.length;
        int sameNum = 1; // Used to count the same number 
        for (int i = 1; i < length; i++) {
            if (array[i] != target) {
                sameNum--;
                if (sameNum == 0) {
                    target = array[i];
                    sameNum = 1;
                }
            } else {
                sameNum++;
            }
        }
        return target;
    }
}

You can also refer to the online problem-solving methods ：

CodeSolution/ The finger of the sword Offer28- A number that appears more than half the times in an array .md at main · Damaer/CodeSolution · GitHub