LeetCode算法题-Third Maximum Number(Java实现-四种解法)

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+篇,