剑指offer之数组出现次数超过一半的数字

1 问题

数组中有一个数字出现了次数超过数组长度的一半,请找出这个数字。

比如{1,2,3,2,2,2,5,4,2},我们知道这个数是2

2 分析

我们数组元素个数分为单数和双数

1)数组长度是单数的情况下

我们有5个元素,里面至少3个2,还有2个元素我们可能重复也可能不重复

我们可以定义一个计数为1,先用变量保存数组第一个数据,然后遍历数组,如果发现后面的数据和前面的数据不一样,我们计数自动减1,如果一样计量数自动加1,当计数为0的时候,我们变量保存数组后面的一个数,比如{2,1,1,2,2},第二个1和第一个2抵消了,我们变量保存了第三个元素,但是第四元素值2和第3元素值也抵消了,最后的值也就是我么需要的值,如果是有2个不重复的数据比如,{1,3,2,2,2},我们第一个元素和第二个元素的值抵消了,当计量等于0就保存数组下一个元素,然后计量数归1,也就是我们保存第三个元素,然后计量加1,到最后,计量大于1,保存的元素就是我们想要的结果。

2)数组长度是双数的情况下

比如6个元素,至少有4个元素一样,2个元素和这4个元素不一样,这2个元素可能重复也可能不重复,和上面的分析也一样,用一个计量和一个变量保存第一个数据,然后后面的元素和前一个元素不一样,我们计量数就自动加1,当计量等于0就保存数组下一个元素,然后计量数归1,最后计量数肯定大于1,然后我们最后保存变量也是我们想要的结果。

3 代码实现

#include <stdio.h>
#include <stdlib.h>

/*
 *检测这个数有没有超过数组元素一半值。
 */
int checkMoreThanHalf(int *datas, int length, int number)
{
    if (datas == NULL || length <= 0)
    {
        return -1;
    }
    int count = 0;
    for (int i = 0; i < length; ++i)
    {
        if (number == datas[i])
            ++count;
    }
    if (count * 2 > length)
        return 1;
    else
        return -1;

}

/*
 *获取超过数组元素一半值这个数
 */
int getMoreThanHalf(int* datas, int length)
{
    if (NULL == datas || length <= 0)
        return 0;
    int result = datas[0];
    int times = 1;
    for (int i = 1; i < length; ++i)
    {
        if (times == 0)
        {
            result = datas[i];
            times = 1;
            continue;
        }
        if (datas[i] == result)
        {
            ++times;
        }
        else
        {
            --times;
        }
    }
    int check = checkMoreThanHalf(datas, length, result);
    if (check)
        return result;
    else
        return -1;
}

int main(void)
{
    int a[] = {2, 1, 2, 3, 2};
    int moreNumber = getMoreThanHalf(a, sizeof(a) / sizeof(int));
    printf("moreNumber is %d\n", moreNumber);
    return 0;
}

4 运行结果

moreNumber is 2

5 另外思路

分析:我们知道剑指offer之partition算法 可以找出一个数据,进行把所有数据分为左边小于其中的一个值,右边的大于一个值,既然题目说了 有一个数字出现了次数超过数组长度的一半,如果数组是奇数个数的话,比如{1,2,3,2,2};我们知道如果排序后最中间的数字就是2,也就是我们的中位数,如果数组是偶数个数的话,比如{1,2,3,2,2,2};这里不能只有3个2,不然3个其他数和题目逻辑矛盾,所以至少是4个2,然后我么进行求这个数组的中位数还是2,所以现在题目演变成了,如果这个数据排序好了,我们求出中位数就行,也就是通过partition算法求出返回值为(数组长度 / 2)的值,然后我们再获取数组下表是值为 数组长度 / 2 的数组值就行。

6 代码实现

#include <iostream>
#include <vector>

using namespace std;

void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void printVector(vector<int> v)
{
    for (int i = 0; i < v.size(); ++i)
    {
        std::cout << v[i] << "\t";
    }
    std::cout << std::endl;
}

/*
 *partition算法 记得如果这里是C++我们传递的是vector类型,我们记得要加引用,
 *不然改变不了数据,这里和java传递ArrayList不一样,ArrayList作为参数可以改变集合里面的值,
 *所以C++如果函数传递非基本数据类型,一半都是带引用的
 */
int partitionOne(vector<int>& vector, int start, int end)
{
    if (start > end)
    {
        std::cout << "vector is empty or start > end" << std::endl;
        return -1;
    }
    int pivot = vector[start];
    while (start < end)
    {
        //我们先从尾巴开始
        while (start < end && pivot <= vector[end])
        {
            --end;
        }
        //这里用的数组赋值,而不是直接用swap交换函数,那么下面的2步也是用数组赋值,而不是用swap交换函数
        vector[start] = vector[end];
        while (start < end && pivot >= vector[start])
        {
            ++start;
        }
        vector[end] = vector[start];

    }
    //std:cout << "start is " << start << "end is " << end << std::endl;
    vector[start] = pivot;
    //printVector(vector);
    return start;
}

void getMoreThanHalf(vector<int>& vector)
{
    if (vector.size() <= 0)
    {
        std::cout << "vector.size is <= 0" << std::endl;
        return;
    }
    int start = 0;
    int end = vector.size() - 1;
    int middle = vector.size() / 2;
    int index = partitionOne(vector, start, end);
    printVector(vector);
    while (index != middle)
    {
        if (index > middle)
        {
          end = index - 1;
          index = partitionOne(vector, start, end);
      }
      else
      {
          start = index + 1;
          index = partitionOne(vector, start, end);
      }
    }
}

int main()
{
    vector<int> v2;
    v2.push_back(2);
    v2.push_back(1);
    v2.push_back(2);
    v2.push_back(3);
    v2.push_back(2);
    v2.push_back(-1);
    v2.push_back(2);

    printVector(v2);

    int a[] = {2, 1, 2, 3, 2};
    getMoreThanHalf(v2);
    std::cout << "value is " << v2[v2.size() / 2] << std::endl;

    return 0;
}

7 运行结果

21232-12
-1122232
value is 2

(0)

相关推荐