package com.interview.sym;
public class TestCountest {
/**
* @param args
* 题目:现在有一个整数数组,已知一个数出现的次数超过了一半,请用O(n)的复杂度的算法找出这个数。
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int candidate = 1 << 31;
int vote = 0;
int arr[] = { 1, 2, 3, 1, 2, 1,2, 1, 1, 5,2, 6 ,2,2,2,2};//该重复数出现的顺序会影响最后vote的值
for (int i = 0; i < arr.length; i++) {
if (arr[i] != candidate) {
if (vote == 0) {
candidate = arr[i];
} else {
vote--;
}
} else {
vote++;
}
}
System.out.print(candidate );
}
}
/*思路:算法:充分利用出现次数超过一半这个特点,使用两个变量candidate和vote,分别代表候选人和票数,遍历数组
按如下方式投票和更换候选人:
若当前数与候选人一样,则把候选人的票数加1
若当前数与候选人不一样, 则把它的票数减1,如果减掉后票数小于0,则把候选人踢掉,用当前数作为新的候选人
最后剩下的候选人就是出现次数超过一半的数。
算法的正确性证明: 数组中,数值相同的数都会投赞成票,数值不同的都会投反对票,有一个数出现的次数超过一半,
其它数得到的反对票必然大于一半,所以其它数中,任何一个得票都会小于0,遭到淘汰。剩下来的只能是超过一半
的那个数。
*/
分享到:
相关推荐
本题是一道经典的查找问题,涉及到的数据规模为:科研调查中获得了一系列的自然数(总数为n),这些数字都不超过1500000000,并且不同的数字不会超过10000个。题目要求在这些数字中查找特定的自然数x,如果找到了,...
本文将探讨如何使用分治策略来解决一个特定的问题——在一个包含n个整数的数组中找到第二大的元素。 #### 分治算法原理 分治(Divide and Conquer)是一种重要的算法设计策略,它通过递归地将一个问题分解成两个或...
在Java编程中,统计一个长整型数字中0到9每个数字出现的次数是一项常见的任务,这在数据处理、分析或者算法实现中都有可能用到。这个任务可以通过使用位操作、数组或者HashMap等数据结构来解决。下面我们将详细介绍...
在C++编程中,有时我们需要找出一个整数数组中的最大值和次大值。这个问题在很多实际应用中都有所体现,比如数据处理、算法分析等。本篇文章将详细讲解如何通过自定义函数来实现这个功能,特别关注的是找出数组中的...
该问题的描述是:已知N个大于0的整数构成一个集合,即{1,2,3,……,N},求其所有的非空且元素不相邻的子集,计算所有子集的乘积的平方的和。 知识点1:子集的概念 子集是集合中的一部分元素的集合。在这个问题中...
在数据结构的学习中,我们经常会遇到寻找数组中最大元素的问题,这是一个基础且重要的算法问题。在Java编程语言中,解决这个问题的方法多种多样,但这里提到的思路是通过逐步比较数组中的元素来找到最大值。这种方法...
算法课本的题目,要求复杂度是(nlgn)。
本篇文章主要探讨如何使用递归算法来实现一个整数的逆序操作,即把一个数字的位数顺序反转过来。例如,将数字1234转换为4321。 #### 知识点概述 1. **递归算法的概念** 2. **递归的基本要素** 3. **递归与循环的...
如果当前基准值的出现次数大于已知的最大众数出现次数,则更新`res`和`resc`。最后,根据基准值两侧的元素数量,递归地在两侧继续搜索众数。 `sortyibian`方法实现了部分快速排序的过程,它选取数组最后一个元素...
可能包含的代码可能是用不同编程语言实现的完美数检测算法,或者是一个包含已知完美数的列表,用于测试和验证算法的正确性。 总的来说,完美数算法的学习可以帮助我们理解因数分解、效率优化以及如何处理大数据等...
基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。在提供的代码中,基数排序用到了一个额外的数组b来记录每个位上的数字出现的情况,并打印出结果。基数排序的...
26、 设计一个O(n2)时间的算法,找出由n个数组成的序列的最长的单调递增子序列。 27、 旅游预算问题。一个旅行社需要估算乘汽车从某城市到另一城市的最小费用,沿路有若干加油站,每个加油站收费不一定相同。旅游...
- **例3:** 给定一个图和一个整数k,判断是否存在一个包含不超过k条边的集合,使得图中的每个顶点至少连接了一条边。这是一个典型的图论问题,可以通过多项式时间算法来解决。 #### 三、NP问题 NP问题是一类可以...
基础判断法是一种非常直观的方法,它通过遍历从2到n-1的所有整数来判断一个数n是否为素数。如果n能被其中任何一个整数整除,那么n不是素数;反之,如果没有任何一个数能整除n,则n是素数。尽管这种方法简单易懂,但...
费马小定理指出,如果n是一个素数,且a是小于n的任意正整数,则a^n mod n等于a。基于此定理,可以提出费马测试:随机选择一个a,如果a^n mod n不等于a,则n很可能是合数。如果经过多次测试后,n仍然是素数的概率很大...
俄式乘法是一种简单的迭代算法,它通过不断将较大的数n分为两半,直到n变为1。如果是偶数,n乘以m就等于n的一半乘以2倍的m;如果是奇数,n乘以m等于(n-1)的一半乘以2倍的m加上m。这个过程会持续到n变成1为止,然后...
它统计每个元素出现的次数,然后根据这些计数来确定每个元素的最终位置。当元素范围较小且分布均匀时,计数排序非常高效,时间复杂度为O(n+k),其中k是整数的范围。然而,如果k接近n,计数排序的空间效率就会下降。 ...
问题:一个排好序的数组 A,长度为 n,现在将数组 A 从位置 m(m<n,m 已知)分开,并将两部分互换位置,设计一个 O(n)的算法实现这样的倒置,只允许使用一个额外空间。 方法:(A’B’)’ = BA 13. 实现 Vector ...
快速排序是一种高效的排序算法,平均时间复杂度为O(n log n)。其核心思想是通过分治法将一个大问题分成若干个小问题来解决。 **算法流程:** 1. 选择一个“基准”元素。 2. 将序列中所有小于基准的元素放在基准左边...
- **解析**:对于一个完全二叉树,第 n 层最多有 \(2^{n-1}\) 个结点,从第 1 层到第 n 层总共最多有 \(\sum_{i=0}^{n-1}2^i = 2^n - 1\) 个结点。正确答案是 A.2^n-1。 **6. 存储程序原理** - **题目内容**:提出...