【蓝桥Java每日一练】——7.至少是其他数字两倍的最大数

2022-05-21 129

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 今天带来的每日一题，是昨天的每日一题——至少是其他数字两倍的最大数。

🐤1.至少是其他数字两倍的最大数

给你一个整数数组 nums ，其中总是存在唯一的一个最大整数。

请你找出数组中的最大元素并检查它是否至少是数组中每个其他数字的两倍。如果是，则返回最大元素的下标，否则返回 -1 。

题目链接：至少是其他数字两倍的最大数https://leetcode-cn.com/problems/largest-number-at-least-twice-of-others/solution/zhi-shao-shi-qi-ta-shu-zi-liang-bei-de-z-985m/

题目分析：题目的要求非常简单，找出一个数组的最大值的下标即可，只不过这个最大值有一个限制条件，它至少是数组中每个其他数字的两倍。大家起码都是大学生了，这意思肯定能看懂吧，无非就是要求最大值最少都都得是次大值的两倍，所以我们遍历一遍数组，利用两个变量maxIndex1和maxIndex2去找到数组中的最大值下标和次大值下标就好啦。

遍历过程：

当我们循环判断nums[i]时，会有三种情况：

1.此时nums[i]>nums[maxIndex1]，nums[maxIndex1]也就是最大值，那么说明找到了个更大的，我们把maxIndex1更新成i

2.此时nums[maxIndex1]>nums[i]>nums[maxIndex2]，找到了个次大值，我们把maxIndex2更新为i

3.此时nums[i]<nums[maxIndex2]，小于次大值，这个数对我们无意义，不处理

最后我们去判断nums[maxIndex1]>=2*nums[maxIndex2]，如果满足我们就输出maxIndex1，否则输出-1

🐣1.易错情况1

上述的逻辑其实是有地方有错误的，不知道大家能否发现，因为根据上述的代码我们会写出如下的代码：

错误版本代码1:
class Solution {
    public int dominantIndex(int[] nums) {
        if(nums.length==1) return 0;
        //1维护的是最大值下标，2维护的是次大值下标
        int maxIndex1=0;
        int maxIndex2=0;
        for(int i=1;i<nums.length;i++){
            if(nums[i]>nums[maxIndex1]){
                 maxIndex2=maxIndex1;                              
            }else if(nums[i]>nums[maxIndex2]){
                 maxIndex2=i;
            }
        }
        if(nums[maxIndex1]>=2*nums[maxIndex2]){
            return maxIndex1;
        }else{
            return -1;
        }
    }
}

这样一写就发现连题目给的第二个用例就过不了：

为什么呢？明明4不是3的两倍，为什么还输出下标3呢？其实如果我们去眼睛debug一下，很容易就会发现一个问题——在情况1中，我们把maxIndex1更新为i，但是没有把maxIndex2更新为maxIndex1。虽然maxIndex1它遇到了比他更大的，但它应该为次大，所以需要把maxIndex1赋值给maxIndex2。

🐣2.易错情况2

如果照上面改正一定就没问题了吧，没错本来我也是这么想的，完善的代码如下：

错误版本2
class Solution {
    public int dominantIndex(int[] nums) {
        if(nums.length==1) return 0;
        //1维护的是最大值下标，2维护的是次大值下标
        int maxIndex1=0;
        int maxIndex2=0;
        for(int i=1;i<nums.length;i++){
            if(nums[i]>nums[maxIndex1]){
                 maxIndex2=maxIndex1;
                 maxIndex1=i;                              
            }else if(nums[i]>nums[maxIndex2]){
                 maxIndex2=i;
            }
        }
        if(nums[maxIndex1]>=2*nums[maxIndex2]){
            return maxIndex1;
        }else{
            return -1;
        }
    }
}

提交以后获得血红的提示：

其实当我一看到这个用例时，我就知道问题出在了哪！我的maxIndex1和maxIndex2起始下标都是0，可是如果num[0]是一个数组的最大元素，那么maxIndex2就不会更新，导致答案出错。我觉得这个还是比较难想到的，究其原因还是因为我的maxIndex1和maxIndex2不合理。但是我们也加一行代码给它强制改正，当nums[maxIndex2]遇到nums[1]比自己小的时候，把maxIndex2更新为1。

🐣3.正确答案版本

结合以上的经验，我们终于写出来AC的代码了：

class Solution {
    public int dominantIndex(int[] nums) {
        if(nums.length==1) return 0;
        //1维护的是最大值下标，2维护的是次大值下标
        int maxIndex1=0;
        int maxIndex2=0;
        for(int i=1;i<nums.length;i++){
            if(i==1&&nums[i]<nums[maxIndex2]){
                maxIndex2=i;
            }
            if(nums[i]>nums[maxIndex1]){
                 maxIndex2=maxIndex1;
                 maxIndex1=i;                              
            }else if(nums[i]>nums[maxIndex2]){
                 maxIndex2=i;
            }
        }
        if(nums[maxIndex1]>=2*nums[maxIndex2]){
            return maxIndex1;
        }else{
            return -1;
        }
    }
}

🐣4.官方答案版本

class Solution {
    public int dominantIndex(int[] nums) {
        int m1 = -1, m2 = -1;
        int index = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > m1) {
                m2 = m1;
                m1 = nums[i];
                index = i;
            } else if (nums[i] > m2) {
                m2 = nums[i];
            }
        }
        return m1 >= m2 * 2 ? index : -1;
    }
}

🐣5.自写版本与官方版本对比总结

自己写的和官方对比起来，肯定是相形见绌。官方版本的优点在于，它用了m1和m2去记录最大值和次大值，只用index去记录最大值下标，且index初始值为-1。迭代最大值m1时才更改index的值。最后的return语句更少一句话搞定，而我反而还写了个ifelse语句。我们为什么要注意去总结？学习算法是循序渐进的路程，虽然我们做出来了，但应该去循环是否有更好的方法、更好的写法以及更好的代码书写规范，这都是我们需要去学习的，只有和更好的人对比才能让自己进步。