提及一条算法题目，查找一个数组中第二大的数。
第二大数，直接想到的是，先遍历一次数组，把最大的取出来。然后再遍历一次，把最大的取出来。总耗费时间复杂度O(n + n -1)
还有没有其他O(n)的算法呢？
先挖坑，在填坑，都到凌晨2点了，明天想下
早上起来，想了下，跟上次连续子数组的思维差不多，用两个数字保存最大的两个数值，大的放前面，第二大的放后面，然后在遍历过程中穷举各种情况即可。
public class kmax{
public static void main(String[] args){
int[] a = new int[]{1,3,-2,32,-3,5};
System.out.println(get2ndMax(a));
}
public static int get2ndMax(int[] a){
//max[0]存放最大值，max[1]存放第二最大值
int[] max = new int[2];
if(a[0]>a[1]){
max[0] = a[0];
max[1] = a[1];
}else{
max[0] = a[1];
max[1] = a[0];
}
for(int i=2;i<a.length;i++){
//穷举，其实就2种情况
if(a[i]>max[0]){
max[1] = max[0];
max[0] = a[i];
}else if(a[i]>max[1]){
max[1] = a[i];
}
}
return max[1];
}
}
去中大打完球回来，除了一身汗，把想到的位图方法也写上吧。编程珠玑中使用位图排序实现了O(n)的排 序，让我大开眼界，原来在特定条件下，O(n)排序也是可能的。既然O(N)的排序都有了，查找第2大的数字也没问题。假定数组的数字都是整数，上限是 MAX，下限是MIN。算法的复杂度是O（2*(MAX-MIN))。
public class BitmapKmax{
public static void main(String[] args){
int[] a = new int[]{-20,-29,32,99,29,10,39,42,28};
System.out.println(get2ndMax(a,-100,100));
}
public static int get2ndMax(int[] a, final int MIN, final int MAX){
if(a.length<2){
throw new IllegalArgumentException("array must contain at least 2 elements");
}
int secondMax = 0;
byte[] byteArr = new byte[(MAX-MIN)/8 + 1];
for (int i=0; i<a.length; i++) {
int v = a[i]-MIN;
int index = v/8;
int v2 = v%8;
byteArr[index] = (byte)(byteArr[index] | (1<<v2));
}
for (int i=0, count=0; i<byteArr.length; i++) {
if(byteArr[i]!=0){
for(int j=0;j<8;j++){
if(0 != (byteArr[i] & (1<<j))){
count++;
}
if(2 == count){
secondMax = i*8 + j;
break;
}
}
if(2 == count){
break;
}
}
}
return secondMax+MIN;
}
}
至于他文章中所说的那个同学没有用O(n)的方法去做，而是用排序，我也挺佩服的。说实话，我也忘了O(nlogn)的快排怎么写了，呵呵，只记得用了分治递归的思想。嗯，下次我也尝试不看书的情况写个快排。
各位看官，不知道有没有其他方法，请不吝笔墨，大书特书。
相关推荐
2. **遍历数组**：从数组的第二个元素开始遍历，对于每一个元素`a[i]`，根据其与当前中位数估计值`mid`的比较结果更新`mid`、`mid_left`和`mid_right`的值。 - 如果`a[i] > mid`且`i`为偶数，那么： - 如果`a[i] ...
"取数组中的第2大值"是一个非常明确的标题，它告诉我们需要从给定的数组中找出第二大的元素的下标和值。这个问题非常常见，在实际编程中经常会遇到这种情况。 描述解释 "c语言实现取数组中的第2大值"是标题的详细...
这篇文章将详细介绍如何在O(n)的时间复杂度内找到数组中的第K大数。 首先，理解这个问题的核心是利用快速排序的分治思想。快速排序通常用于对整个数组进行排序，但在这里我们并不需要完全排序，而是只需要找到第K大...
2. 随机访问：数组可以随机访问，这意味着我们可以通过索引直接访问数组中的任何元素。这是因为数组的元素在内存中是连续的，因此我们可以通过索引来计算元素的地址。例如，vector的随机访问可以通过iterator i = v....
然后，通过一个for循环从数组的第二个元素开始遍历，如果当前元素大于已知的最大值，就更新最大值。当遍历完整个数组后，返回找到的最大值。 这种方法虽然简单，但效率并不高，因为它的时间复杂度是O(n)，其中n是...
选择排序的时间复杂度为O(n^2)，在数据量较大时效率较低。为了提高性能，可以考虑以下几种优化方案： 1. **使用更高效的排序算法**：如快速排序或归并排序，它们的时间复杂度通常为O(n log n)。 2. **部分排序**：...
- **遍历**：从数组的第二个元素开始，逐个与当前的最大值和次最大值进行比较。 - **更新逻辑**： - 如果当前元素大于最大值\( x \)，则将\( x \)的值赋给\( y \)，并将当前元素赋值给\( x \)。 - 如果当前元素...
- 程序的时间复杂度为O(n*m)，其中n是行数，m是列数。这是因为程序需要遍历数组的每一个元素。 - 空间复杂度为O(1)，除了输入数组之外，只使用了固定的几个变量来存储中间结果。 5. **扩展性**： - 可以通过修改...
在这个问题中，我们需要确保算法的空间复杂度为O(1)，这意味着我们不能使用额外的大规模存储空间，只能在原数组上进行操作。 首先，我们要理解循环右移的概念。假设有一个数组`a[0..n-1]`，循环右移m位意味着数组的...
插入排序在小规模或者部分有序的数据中表现良好，其最好情况（已排序数组）的时间复杂度为O(n)，最坏情况（反序数组）为O(n^2)，平均情况为O(n^2)。 **希尔排序**是插入排序的一种优化版本，通过设置一个增量序列，...
这段代码的效率相当高，因为它只需要遍历一次数组，时间复杂度为O(n)，其中n是数组中的元素总数。此外，由于我们直接对数组进行操作，没有使用额外的数据结构，所以空间复杂度为O(1)。 总之，通过使用嵌套循环和...
2. 遍历数组，从第二个元素（下标为1）开始。 3. 对于每个元素，如果它的值小于当前的最小值，更新minIndex1为当前元素的下标；如果它的值大于等于最小值但小于当前的次小值，更新minIndex2。 4. 遍历完成后，...
一次遍历的时间复杂度为O(n)，其中n是数组的长度，因为只需要遍历数组一次。而排序会引入额外的时间开销，如果使用快速排序、归并排序等高效排序算法，时间复杂度大约为O(n log n)。但是一旦排序完成，查找最大差值...
- 计算效率不高，因为每次迭代都需要乘以前一个元素，对于大规模数据，时间复杂度较高，为O(N)。 在实际应用中，我们还可以考虑其他优化策略，如使用动态规划减少不必要的计算，或者使用更高效的数据结构，如链表。...
1. **遍历检查**：最直观的方法是两层循环遍历数组，第一层遍历数组元素，第二层检查其余元素是否有相同的值。这种方法的时间复杂度为O(n^2)，效率较低，但实现简单。 2. **排序后查找**：可以先对数组进行排序，...
这个问题的一个著名解决方案是Kadane's Algorithm（卡丹算法），它具有线性时间复杂度，即O(n)，其中n是数组的长度。 首先，我们需要理解什么是子数组。在数组中，子数组是指从数组中选取任意连续的一段元素形成的...
2. 查找第二大、第三小等值： - 遍历法：在已排序数组中，找到最大值后，再遍历一次数组找到次大值。 - 优先队列（堆）：使用最大堆结构，可以快速找到最大的k个元素。 三、排序算法的时间复杂度和稳定性 时间...
这两种方法都是线性时间复杂度，即 O(n)，其中 n 是数组的长度。虽然在最坏的情况下都需要遍历整个数组，但它们都避免了使用额外的数据结构（如堆或排序），因此在空间效率上表现良好。对于小规模的数据，这种效率是...
但是，这种方法的时间复杂度较高（O(n^2)），因为每次移动都需要复制整个数组。为了提高效率，我们可以采用以下优化方法： 1. **反转法**：首先反转整个数组，然后反转前M个元素，最后反转剩余的元素。这样，通过三...