Open bitfishxyz opened 5 years ago
这题看起起来简单,其实要考虑各种情况,综合起来挺复杂的。
为了方便,可以专门的写一个新的数据结构。
import java.util.Arrays;
import java.util.Set;
class Solution {
/**
* 构造一个新的数据结构,来存储前三大的数字
*/
private class ThisSet {
/**
* 数据结构的容量,在[0, 3] 之间
*/
private int size = 0;
/**
* 底层数组,当容量小于3时,这个数组后面的元素将被忽略
*/
private int[] arr = new int[3];
/**
* 获得当前数组中的最小值的索引
* @return
*/
private int getIndexOfMinValue(){
assert size > 0;
int minIndex = 0;
for (int i = 1; i < size; i++) {
if (arr[i] < arr[minIndex]){
minIndex = i;
}
}
return minIndex;
}
/**
* 看看这个数据结构中是否包含了目标值
* @param thisValue
* @return
*/
private boolean contains(int thisValue){
for (int i = 0; i < size; i++) {
if (arr[i] == thisValue){
return true;
}
}
return false;
}
/**
* 这个数据结构的特点就是插入时不维护数组的有序性,需要的时候再排序
* @param newValue
*/
public void add(int newValue){
// 数组中已经存在对应元素了,忽略这次插入
if (contains(newValue)){
return;
}
if (size < 3){
arr[size] = newValue;
size++;
} else {
int indexOfMinValue = getIndexOfMinValue();
arr[indexOfMinValue] = Math.max(arr[indexOfMinValue], newValue);
}
}
/**
* 这个数组的最小值就是第三大的元素
* @return
*/
public int getThirdValue(){
if (size == 0) {
throw new RuntimeException("没有元素");
}
if (size == 1) {
return arr[0];
}
if (size == 2) {
return Math.max(arr[0], arr[1]);
}
return arr[getIndexOfMinValue()];
}
}
public int thirdMax(int[] nums) {
ThisSet set = new ThisSet();
for (int value : nums) {
set.add(value);
}
return set.getThirdValue();
}
}
给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
示例 1:
示例 2:
示例 3: