寻找数组中第二小的元素
方法一：用选择排序，冒泡法，或者交换排序这类的排序 先把数组进行升序排序 排完序后再进行遍历比较。排序算法中效率最高的时间复杂度为O(nlnogn)
public static void main(String[] args) {
int arr[]={-4,-4,56,34,76,34,23,4,75,87,50,3,5,6,};
//冒泡排序
for(int i=0;i<(arr.length)-1;i++){
for(int j=0;j<arr.length-i-1;j++){
if(arr[j]>arr[j+1]){
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
int secondNum=arr[0];
for (int i=0;i<arr.length;i++){
if(arr[i]>secondNum){
secondNum=arr[i];
break;
}
}
System.out.println("secondNum---->"+secondNum);
}方法二：遍历数组,找出最小的两个数字。时间复杂度为O(n)
public static void main(String[] args) {
int arr[]={-87,-97,23,90,12,-87,-87};
int firstmin = Integer.MAX_VALUE; //第一小的元素 初始值设为int的最大取值
int secondmin = Integer.MAX_VALUE; //第二小的元素 初始值设为int的最大取值
for(int value:arr){
if (value < firstmin) //小于最小的元素 更新1和2
{
secondmin = firstmin;
firstmin = value;
}
else if (value < secondmin && value != firstmin) //小于倒数二的 更新2
{
secondmin = value;
}
}
System.out.println("firstmin--------->"+firstmin);
System.out.println("secondmin--------->"+secondmin);
}方法三：用快速排序的思想。算法复杂度是O(N)
public static void main(String[] args) {
int arr[]={34,12,23,90,12,-87,-27};
Arrays.sort(arr); //排序 升序
int secondNum=arr[0];
for(int i=1;i<arr.length;i++){
if(arr[0]<arr[i]){
secondNum=arr[i];
break;
}
}
System.out.println(secondNum);
}方法四：第四种方法很是简单，但是使用它需要某个条件，也就是输入数组的取值范围很小，最好的情况是能形成完全分布，也就是1000大小的数组里面的数字是从1到1000这样子。首先，生成一个能够完全装下原数组的数组，这个地方的装下是指数组大小等于原数组最大元素（也许还有优化，但这么描述简单一点），比如原数组是[1,2,3,4,5],我要生成的数组大小是5，如果原数组是[5,3,6,10]，我要生成的数组大小是10。接下来遍历原数组，把每一个元素放到第二个数组对应的下标处，5就放在下标为5的地方（实际过程中要减1，因为是数组从0开始）。放的过程中增加元素值用来统计这个元素出现的次数。这一过程算法复杂度是O(N)。接下来，再遍历生成的数组，找出第K大的元素。这个过程的算法复杂度是多少呢？其实这个和原数组很有关系，原数组越离散也就越糟糕。比如原数组是[1,1000]，这样就十分糟糕。第二部的算法复杂度是O(M)，M是前数组的最大值。总的算法复杂度O(N)+O(M); 方法五：第五种方法是用二叉堆来做。对大小为N的数组构建二叉堆的算法复杂度是O(N)。然后每次下滤的算法复杂度是O(logN)，一共下滤K次，算法复杂度是O(N+K*logN)。这种做法比较适合用来处理输入数组极大的情况，原因是如果输入数组大到不能放入内存，那么构建二叉堆（优先队列）的时候就可以只构造一个K个元素的优先队列。如果下一个元素比这个最大堆的堆顶还大就直接pass。第二个原因是算法二在对付一个极大的输入队列的时候算法复杂度的一个常数会很大。