LeetCode算法题-Third Maximum Number(Java实现-四种解法)
这是悦乐书的第222次更新,第235篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第89题(顺位题号是414)。给定非空的整数数组,返回此数组中的第三个最大数字。如果不存在,则返回最大数量。时间复杂度必须在O(n)中。例如:
输入:[3,2,1]
输出:1
说明:第三个最大值为1。
输入:[1,2]
输出:2
说明:第三个最大值不存在,因此返回最大值2。
输入:[2,2,3,1]
输出:1
说明:请注意,此处的第三个最大值表示第三个最大不同的数字。值为2的两个数字都被视为第二个最大值。
本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。
02 第一种解法
使用包装类Integer,分别定义第一大、第二大、第三大三个变量。foreach遍历数组中的每个元素,如果当前元素与三个变量中的任意一个相等,就进入下一次循环。如果第一大为null或者当前元素大于第一大,那么将三个数轮流交换位置,第三大为原第二大,第二大为原第一大,第一大为当前元素。如果第二大为null或者当前元素大于第二大,那么第三大为原第二大,第二大为当前元素。如果第三大为null或者当前元素大于第三大,那么第三大为当前元素。最后,如果第三大为null,就返回第一大,反之返回第三大。
此解法时间复杂度是O(n),空间复杂度是O(1)。
public int thirdMax(int[] nums) {
Integer max_one = null;
Integer max_two = null;
Integer max_three = null;
for (Integer n : nums) {
if (n.equals(max_one) || n.equals(max_two) || n.equals(max_three)) {
continue;
}
if (max_one == null || n > max_one) {
max_three = max_two;
max_two = max_one;
max_one = n;
} else if(max_two == null || n > max_two) {
max_three = max_two;
max_two = n;
} else if (max_three == null || n > max_three) {
max_three = n;
}
}
return max_three == null ? max_one : max_three;
}
03 第二种解法
此解法的思路和第一种解法的思路一致,只是将包装类Integer换成了long类型,去掉了equals方法。
此解法时间复杂度是O(n),空间复杂度是O(1)。
public int thirdMax2(int[] nums) {
long max_one = Long.MIN_VALUE;
long max_two = Long.MIN_VALUE;
long max_three = Long.MIN_VALUE;
for (int n : nums) {
if (n == max_one || n == max_two || n == max_three) {
continue;
}
if (max_one == Long.MIN_VALUE || n > max_one) {
max_three = max_two;
max_two = max_one;
max_one = n;
} else if (max_two == Long.MIN_VALUE || n > max_two) {
max_three = max_two;
max_two = n;
} else if (max_three == Long.MIN_VALUE || n > max_three) {
max_three = n;
}
}
return max_three == Long.MIN_VALUE ? (int)max_one : (int)max_three;
}
04 第三种解法
此解法和上面两种思路类似,但是将首次相等的判断做了调整,如果当前元素大于等于第一大或第二大或第三大时,再去继续判断是不是大于第一大或第二大或第三大,满足才交换位置。
此解法时间复杂度是O(n),空间复杂度是O(1)。
public int thirdMax3(int[] nums) {
long one = Long.MIN_VALUE;
long two = Long.MIN_VALUE;
long three = Long.MIN_VALUE;
for (int n : nums) {
if (n >= one) {
if (n > one) {
three = two;
two = one;
one = n;
}
} else if (n >= two) {
if (n > two) {
three = two;
two = n;
}
} else if (n >= three) {
if (n > three) {
three = n;
}
}
}
return three == Long.MIN_VALUE ? (int)one : (int)three;
}
05 第四种解法
特殊情况:当数组中只有一个元素时,此时第三大的值就是该元素;当数组中只有两个元素,那么第三大元素就是两元素中最大的一个。
正常情况:使用Arrays.sort()方法,先将数组排序,从小到大排列,定义一个变量count,从后往前遍历,如果当前元素和前一个元素相等,就跳出当前循环进入下一次循环,否则count就加1。然后判断count是否等于2,因为第一大和第二大不相等时,count才加1,第二大和第三大不相等时,再加1,所以当count等于2时,就表示遇到了第三大的数,对应的索引是i-1,不是i。如果不满足,最后返回第一大的数即可。
此解法的时间复杂度是O(nlog(n)),空间复杂度是O(1)。
public int thirdMax4(int[] nums) {
int length = nums.length;
if (length == 1) {
return nums[0];
}
if (length == 2) {
return Math.max(nums[0], nums[1]);
}
Arrays.sort(nums);
int count = 0;
for (int i=length-1; i>0; i--) {
if (nums[i] == nums[i-1]) {
continue;
} else {
count++;
}
if (count == 2) {
return nums[i-1];
}
}
return nums[length-1];
}
06 小结
算法专题目前已连续日更超过两个月,算法题文章89+篇,