变量设计,一个变量,存数num,另一个存这个数出现的次数times.
初始:num存第一个数,times表示num出玩的次数为1
当遇到num这个数,times就加1,没有遇到就times减1。当times为0时,也就是num中没有计数了,也就是当一个新数进来时,就开始计数。
继续这样去遍历。。。。。。
int MoreThanHalfNum(int *a , int n ) { int i , k , num = a[0]; int times = 1; for(i = 1 ; i < n ; ++i) { if(times == 0) { num = a[i]; times = 1; } else if(a[i] != num) --times; else ++times; } k = 0; for(i = 0 ; i < n ; ++i) { if(a[i] == num) ++k; } if(k*2 <= n) return -1; //没有找到 else return num; //找到 }
相关推荐
在两个正序数组中找中位数,我们需要合并这两个数组并找出中位数,但要求是尽可能地减少操作次数,因为这直接影响到算法的效率。 C++作为一门强大的编程语言,它提供了丰富的数据结构和算法工具来解决这类问题。...
#### 一、数组中出现次数超过一半的数字 本节主要探讨了如何在数组中找到出现次数超过数组长度一半的数字。这个问题在实际的编程和算法面试中非常常见,其背后的逻辑对于理解数据结构与算法优化具有重要意义。 **...
1. **超过一半的数字**:这个问题要求找出数组中出现次数超过一半的元素,可以采用摩尔投票法,通过两两抵消的方式快速找到多数元素。 2. **调整数组顺序**:将数组中的奇数移动到偶数前面,同时保持它们之间的相对...
数组中出现次数超过一半的数字 最小的k个数 数组中的第K个最大元素 把数组排成最小的数 存在重复元素 打乱数组 三数之和 化栈为队 144.二叉树的前序遍历 146.LRU缓存机制 155.最小栈 31.栈的压入、弹出序列 32.从上...
【POJ 3693】的问题更复杂一些,需要找出字符串中重复次数最多的连续重复子串。此时,我们需要枚举循环节长度和起点,计算后缀的最长公共前缀,从而确定循环节的长度和位置。 【POJ 3294】中,我们需要找到一个子串...
**题解**: 给定一个非空数组,返回众数(即出现次数超过数组一半的数)。 **算法**: - 使用 Boyer-Moore 投票算法。 - 遍历数组,维护一个候选众数和一个计数器。 - 如果当前元素与候选众数相同,则增加计数器;...
冒泡排序是一种直观的排序方法,通过重复遍历数组,每次比较相邻两个元素并根据需要交换它们的位置,使得较大的元素逐渐“浮”到数组的顶端。其核心是两层循环结构,外层控制遍历次数,内层负责相邻元素的比较与交换...
13. **数组中出现次数超过一半的数字**:摩尔投票法(Majority Voting Algorithm)是解决这类问题的经典方法。 14. **数组中最小的 k 个数**:可以使用快速选择算法或者优先队列(堆)来寻找最小的k个数。 15. **...
首先,取数组的第一个、最后一个和中间元素,找出三个中最小的作为新的枢轴,然后根据枢轴的位置将数组分为三部分:小于枢轴、等于枢轴和大于枢轴。如果k在小于枢轴的区间,就在这个区间重复此过程;如果k在大于枢轴...
这是因为每次比较后,搜索区间都会减少一半,这种对半分割策略极大地减少了不必要的比较次数。 ### 结论 通过上述分析,我们可以看出二分法查找在处理有序数组查找问题时的强大优势。然而,值得注意的是,算法的...
38. 数字在排序数组中出现的次数:需要找到数字出现的边界,即第一个等于和最后一个等于数字的位置。 39. 二叉树的深度:是二叉树节点数最多的路径长度,可以通过递归或层序遍历(层数计数)求得。 40. 数组中只...
本文将探讨一个常见的编程问题,即在给定的数组中找到众数,即出现次数超过数组长度一半的元素。这个问题来源于LeetCode上的热门题目,具有较高的实践价值。 首先,我们来看一种直观但效率较低的方法——投票筛选法...
2. 统计数组中每个元素的出现次数,如果有元素出现次数大于1,则存在重复。 #### 219.ContainsDuplicateII **题目描述:** 给定一个整数数组 `nums` 和一个正整数 `k`,判断数组中是否存在两个不同的索引 `i` 和 `...
3. **计数排序**:如果数组中的元素范围不是特别大,可以使用计数排序预处理出每个元素出现的次数,然后根据计数结果找到第k小的元素。这种方法的时间复杂度为O(n + k),空间复杂度为O(max_val),其中max_val是数组...
如数组中出现次数超过一半的数字、两个链表的第一个公共节点等题目。 3. **字符串**:字符串处理题目包括替换空格、表示数值的字符串、字符串的排列、把数字翻译成字符串等,涉及到字符串操作、动态规划等。 4. **...
在示例中,数组元素被用作基数,创建了一个新的计数数组b,用于记录每个数字出现的次数。最后,根据计数数组打印出原始数组的排序结果。 4. **插入排序 (Insertion Sort)**: 插入排序是一种简单直观的排序算法,...
如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。 ##...
在代码示例中,数组`a`初始化为`{1,5,9,7}`,通过创建一个大小为10的辅助数组`b`,用于统计每个数字出现的次数,最后遍历辅助数组来输出原数组的排序结果。 ### 插入排序(Insertion Sort) 插入排序是一种简单...
另外,还可以解决寻找出现次数超过数组长度一半的数字的问题,可以借助快速排序的思想或使用最大堆等数据结构。 总的来说,排序算法是计算机科学的基础,理解和掌握这些算法对于优化程序性能、解决实际问题具有重要...
在这个例子中,数组中的六个数通过两层循环实现冒泡排序,外层循环控制遍历次数,内层循环进行相邻元素的比较和交换。每次遍历结束后,最大的元素会被“冒泡”到数组末尾。 5. 猴子吃桃问题: 这是一个关于递推问题...