Numbers that appear more than half the time in the array (C++ Swordfinger Offer details)


The first time I saw this question, it was so simple as to burst. Or sort function sorting, median, traversing the number of times is OK?But during an interview, sort may let you do it yourself, or the title requires: Can't you modify the input array???
The first method (based on the Partition function)
Note: This method modifies the input array

Core: A number that occurs more than half the time, and the median must be that number after sorting

Solution ideas: Randomly select an element in the array through the Partition function (default in my code is the first element in the array), and with the idea of fast-pacing, small elements move in front of random values, large elements move behind random values, and then return to the last position of random values.Then, by calling the Partition function, use the returned index value and median value to determine whether the median is on the left, end=mid-1, or index<mid, the median is on the right, start=mid+1 until it is finally equal to mid, then numbers[mid] is the number that occurs most, and finally, by using the Check function, determine if the number of occurrences exceeds half of the array.

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers)
    {
        int length = numbers.size();
        if (length <= 0)//Send blank
            return 0;
        int start = 0;
        int end = length - 1;
        int index = Partition(numbers, start, end);//The position of the random value of the Partition function in the array
        int mid = length >> 1;//Statistical Median
        while (index != mid)//Random Value and Median Position Criterion
        {
            if (index>mid)
            {
                end = index - 1;
                index = Partition(numbers, start, end);
            }
            else if (index<mid)
            {
                start = index + 1;
                index = Partition(numbers, start, end);
            }
        }
        if (!Check(numbers, numbers[index]))//Determine if more than half the time
            return 0;
        return numbers[index];
    }
    int Partition(vector<int> num, int start, int end)
    {
        int index = start;
        int sum = num[start];//The default random value is first, where you can use the Random Function
        //Start with the second
        for (int i = start + 1; i<end; ++i)
        {
            if (num[i]<sum)
            {
                ++index;
                swap(num[i], num[index]);
            }
        }
        swap(num[start], num[index]);//Random value centered (small left, large right)
        return index;
    }
    bool Check(vector<int> num, int result)
    {
        int count = 0;
        for (int i = 0; i<num.size(); ++i)
        {
            if (num[i] == result)
                ++count;
        }
        if (count * 2>num.size())
            return true;
        return false;
    }
};

Second method (counting)
Note: This method does not modify the input array

Core: Number of digits that occur more than half the time is at least one more than all other numbers

Solve the problem by starting at the first place (result==numbers[0]), encountering equal elements, count++, encountering unequal elements, count--, when count==0, result is reassigned to the current element, count is reassigned to 1, until after the array has been traversed, result is returned

Doubt???Now that we can figure out why we should call the Check function, because we can't tell if result is the most frequent element, even if it is the most frequent element, and if it is more than half of the array, for example: {5,5,5,5,5,3,3,3,4,4,4} {3,3,4,4,4,5,5}

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.size()<=0)
            return 0;
        int result=numbers[0];
        int i=1;
        int count=1;
        for(;i<numbers.size();++i)
        {
            if(count==0)
            {
                result=numbers[i];
                count=1;
            }
            else if(result==numbers[i])
                ++count;
            else
                --count;
        }
        if(!Check(numbers,result))
                result=0;
        return result;
    }
    bool Check(vector<int> num,int result)
    {
        int count=0;
        for(int i=0;i<num.size();++i)
        {
            if(num[i]==result)
                ++count;
        }
        if(count*2>num.size())
            return true;
        return false;
    }

Tags: C++

Posted on Fri, 07 Feb 2020 22:11:55 -0800 by bluntster