C解OJ题--多数元素（诸侯争霸与管子里的蛇）

2024-02-02 08:14:28

原题如下：

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

审题：
多数元素指的就是这组数据的众数，本题的突破点是：多数元素的出现次数比数组大小的一半还要多。

诸侯争霸：
多数元素，将是这组数据中出现次数最多的元素。将这组数据中的元素分别看成一个诸侯国，它们之间进行打仗，并且它们之间都能一对一同归于尽。那么最后的获胜者将是人口最多的诸侯国。
起初采用混战的状态，在征战中，遇见同样的就将人口数加一，否则一对一消耗。如果该国家的人口变为了0，则更改获胜者。最后的获胜者将是人口最多的，即多数元素。现有如下一组数据：
C解OJ题--多数元素（诸侯争霸与管子里的蛇）
起初假设获胜者是2这个数据,人口数为1。与后面的数据进行混战，先与数组下标为1的进行对战，两个数据一样进行收编，人口数变为2。再与下标为2的进行交战，数据不一样，则一对一消耗，人口数变为1……
当与3号位置交战完毕后，曾经假设的获胜者人口数变为0，则更改假设获胜者为1这个数据，将其人口数改为1，再进行混战……最后胜者将会是2这个数据。

代码实现：

int majorityElement(int* nums, int numsSize){
    int winner=nums[0];//假设获胜者是数组下标为0的这组数据
    int count=1;//初始人口数为1
    for(int i=1;i<numsSize;i++)//进行混战
    {
        if(nums[i]==winner)//数据一样则进行收编
        {
            count++;//人口数增加1
        }
        else//不一样则进行一对一消耗
        {
            count--;//人口数减1
        }
        if(count==0)//如果人口数变为了0，则更改获胜者
        {
            winner=nums[i];
            count=1;
        }
    }
    return winner;//最后的获胜者将是还用人口的数据
}

砍管子里的蛇：
现有如下的一组数据：
C解OJ题--多数元素（诸侯争霸与管子里的蛇）
对其按升序排序如下：

将多数元素看成一条蛇，将数组看成一根管子。如果我们从管子的二分之一处砍下去，一定可以砍到这条蛇。这个很好理解，多数元素将会占据数组的大半位置。
基于这种思想，我们优先对数据进行一次排序，再返回数组二分之一处的数据。所以排序的各种算法，就是大家所要考虑选择的。
此处我们选择直接插入排序

代码实现：

int majorityElement(int* nums, int numsSize){
    int i;//用于标记无序组下标的位置
    int j;//用于标记有序组下标的位置
    int temp;//临时变量，临时存储数据
    for(i=1;i<numsSize;i++ )//数据第一个位置默认有序，遍历无序组数据
    {
        temp=nums[i];//将待插入数据进行拷贝
        for(j=i-1;j>=0&&nums[j]>temp;j--)
        {
            nums[j+1]=nums[j];//将数据往后移动
        }
        nums[j+1]=temp;//插入到比较位置的下一个位置
    }
    return nums[numsSize/2];//返回二分之一处的数据
}

用这种排序方式的时间复杂度还是挺高的。关于各种排序算法在往期的文章中都有详细介绍，包括代码实现。这里就不重复讲解了，感兴趣的话大家可以看看。

我是老胡，感谢阅读！！ ❤️ ❤️

码农公寓

相关文章