程序1.0
思想：现将数组排序，再找出元素
计算
安全
数据库
网络和加速
企业服务
void Arraysort(int *a, int length)//冒泡O(n^2)
{
for (size_t i = 0; i < length; i++)
{
for (size_t j = 1; j <length - 1 - i; j++)
{
if (a[j]>a[j + 1])
swap(a[j], a[j + 1]);
}
}
}
int MorethanHalfNumber(int *a, int length)
{
Arraysort(a, length);
int count = 1;
for (size_t i = 0; i < length-1; i++)
{
if (a[i] == a[i + 1])
{
count++;
if (count == (length + 1) / 2)
return a[i];
}
else
count = 1;
}
return 0;
}时间复杂度太大，不好
程序1.1 改进
思想：如果数组中的一个数字出现的次数超过数组长度的一半，如果要排序，那么排序之后位于数组中间的数字一定就是那个出现次数超过数组长度一半的数字
利用快速排序，先在数组中随机选择一个数字，然后调整数字中数字的顺序，使比选中的数字小数字都排在左边，反之则在右边，如果选中的数字下标为n/2,那么这个数字就是数组的中位数，如果选中的数字下标大于n/2则中位数在左边，接着在它的左边部分的数组中查找。。。利用递归完成
bool CheckMoreThanHalf(int *a, int length, int number)
{
int count = 0;
for (int i = 0; i < length; i++)
{
if (a[i] == number)
count++;
}
if (count * 2 <= length)
return false;
return true;
}
int MorethanHalfNumber(int *a, int length)
{
if ((a == NULL) || length <= 0)
return 0;
int mid = length >> 1;
int start = 0;
int end = length - 1;
int index = Partition(a, length, start, end);//快排
while (index != mid)
{
if (index > mid)
{
end = index - 1;
index = Partition(a, length, start, end);
}
else
{
start = index + 1;
index = Partition(a, length, start, end);
}
}
int result = a[mid];
if (!CheckMoreThanHalf(a, length, result))
result = 0;
return result;
}程序2.0
根据数组特点找出O(N)算法
在遍历数组的时候保存两个值，一个数组的第一个数字，一个是次数，当遍历到下一个数字时，若果下一个数字和我们之前保存的数字相同，则次数加1，如果下一个数字和之前保存的数字不同，次数减1，如果次数为0，我们保存下一个数字，并把次数设为1。由于要找的数字出现的次数一定比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为1时的数字
bool CheckMoreThanHalf(int *a, int length, int number)
{
int count = 0;
for (int i = 0; i < length; i++)
{
if (a[i] == number)
count++;
}
if (count * 2 <= length)
return false;
return true;
}
int MorethanHalfNumber(int *a, int length)
{
if ((a == NULL) || length <= 0)
return 0;
int result = a[0];
int count = 1;
for (int i = 1; i < length; i++)
{
if (count == 0)
{
result = a[i];
count = 1;
}
else if (a[i] == result)
count++;
else
count--;
}
if (!CheckMoreThanHalf(a, length, result))
result = 0;
return result;
}亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
