subject

There is a number in the array that occurs more than half the length of the array. Find the number. For example, enter an array {1,2,3,2,2,2,5,4,2} with a length of 9. Since the number 2 appears five times in the array, more than half the length of the array, output 2. If not, output 0.

Solving problems

Method 1: An algorithm based on Partition function with time complexity O(n)

This algorithm is inspired by the fast sorting algorithm. In the Random Quick Sort algorithm, we first randomly select a number in the array, and then adjust the order of the numbers in the array so that the numbers smaller than the selected number are on its left side and the numbers larger than the selected number are on its right side. If the subscript of the selected number is exactly n/2, then the number is the median of the array; If its subscript is greater than n/2, then the median should be on its left side, and we can then look in the array of its left part. If its small scale is less than n/2, then the median should be on its right side, and we can then look in the array in its right part. This is a typical recursive process that can be implemented with the following code:

class Solution
{
public:
	bool g_bInputInvalid = false;
	//Primary function, where Partition is implemented in Random Quick Sort
	int MoreThanHalfNum(int*numbers, int length)
	{
		if (CheckInvalidArray(numbers, length))
			return 0;
		int middle = length >> 1;
		int start = 0, end = length - 1,index=Partition(numbers,length,start,end);
		while (index != middle)
		{
			if (index > middle)
			{
				end = index - 1;
				index= Partition(numbers, length, start, end);
			}
			else
			{
				start = index + 1;
				index = Partition(numbers, length, start, end);
			}
		}
		int result = numbers[index];
		if (!CheckMoreThanHalf(numbers, length, result))
		{
			result =0;	
		}
		return result;
	}
	//Determine if the number exceeds half the length of the array
	bool CheckMoreThanHalf(int *numbers, int length, int number)
	{
		int times = 0;
		for (int i = 0; i < length; ++i)
		{
			if (numbers[i] == number)
				times++;
		}
		bool isMoreThanHalf = true;
		if (times * 2 <= length)
		{
			//g_bInputInvalid = true;
			isMoreThanHalf = false;
		}
		return isMoreThanHalf;
	}
	//Judging outlier functions
	bool CheckInvalidArray(int *numbers, int length)
	{
		g_bInputInvalid = false;
		if (!numbers || !length)
			g_bInputInvalid = true;
		return g_bInputInvalid;
	}
};

Method 2: Find an algorithm with O(n) time complexity based on the characteristics of the array

A number in an array occurs more than half the length of the array, meaning it occurs more than the sum of all the other numbers. So we can consider saving two values when traversing an array: one is a number of arrays and the other is a number of times. When we traverse to the next number, if the next number is the same as the number we saved before, add 1 times. If the next number is different from the one we saved before, subtract one. If the number is zero, we need to save the next number and set the number to 1. Since the number we are looking for appears more often than the sum of all the other numbers, the number we are looking for must be the number that corresponds to the last time we set the number to 1.

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.empty()){
            return 0;
        }
        // Traverse each element and record the number of times; If the same as the previous element, the number is added 1, otherwise the number is subtracted 1
        int result = numbers[0];
        int times = 1;
        for(int i = 1; i < numbers.size(); ++i){
            if(times == 0){
                // Update result value is current element, collocation number is 1
                result = numbers[i];
                times = 1;
            }
            else if(numbers[i] == result){
                times++;
            }
            else{
                times--;
            }
        }
        // Determine if the result meets the criteria, that is, it occurs more than half the length of the array
      if (!CheckMoreThanHalf(numbers, length, result))
		{
			result =0;	
		}
		return result;
};

Solution Comparison

The time complexity of both algorithms is O(n). The analysis of the time complexity of the algorithm based on the Parition function is not very intuitive. We note that in the first solution, the order of the numbers in the array needs to be exchanged, which modifies the input array. Can I modify the input array? During the interview, we can discuss with the interviewer to make him clear. If the interviewer says the input array cannot be modified, the second solution is the only one.