求数组中第三大的数字,如果不存在则返回最大的数字
要求:算法时间复杂度为O(n)。
代码:
public int getThirdMaxElement(int[] array) { if(array == null) { return 0; } if(array.length == 1) { return array[0]; } if(array.length == 2) { return array[0] > array[1] ? array[0] : array[1]; } int[] thirdArr = {0,0,0}; //数组存储最大的三个数 int a = 0; //thirdArr数组下标 int b = 1; //array数组下标 thirdArr[0] = array[0]; //填充thirdArr数组 while(a < 2 && b < array.length) { if(thirdArr[a] != array[b]) { thirdArr[a+1] = array[b]; a++; } b++; } if(a < 2) { //如果thirdArr只有两个元素 return thirdArr[0] > thirdArr[1] ? thirdArr[0] : thirdArr[1]; } else { //对thirdArr数组排序 Arrays.sort(thirdArr); //升序 } //对剩余数组进行比较 while(b < array.length) { if(thirdArr[2] < array[b]) { //1.最大的数比较 thirdArr[0] = thirdArr[1]; thirdArr[1] = thirdArr[2]; thirdArr[2] = array[b]; b++; continue; } if(thirdArr[1] < array[b]) { //2.中间数比较 thirdArr[0] = thirdArr[1]; thirdArr[1] = array[b]; b++; continue; } if(thirdArr[0] < array[b]) { //3.最小的数比较 thirdArr[0] = array[b]; b++; continue; } b++; } return thirdArr[0]; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。