一道十分简单但仍然学到不少的题目。
同样属于数组类,是int型数组的计算问题。

将问题抽象转换为一个关系式,然后用最巧妙的方式判断是否满足,就可以得到最优解。

题目

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

在一个给定的数组nums中,总是存在一个最大元素 。
查找数组中的最大元素是否至少是数组中每个其他数字的两倍。
如果是,则返回最大元素的索引,否则返回-1。

来源:力扣(LeetCode),详见👇
链接:https://leetcode-cn.com/problems/largest-number-at-least-twice-of-others

理解

最大元素至少是其它数字的两倍,那么 最大元素 > 第二大元素的两倍
所以把数组排个序,然后判断上面这个是否成立即可,后面的其它数字自然成立。

常规思路

知道Java有个sort方法,上手就是一个「直译」脑中的想法:

class Solution {
    public int dominantIndex(int[] nums) {
        if (nums.length == 1)
            return 0;
        if (nums.length == 2)
            return nums[0] >= nums[1] ? 0 : 1;
        int[] bNums = (int[]) Arrays.copyOf(nums,nums.length) ;
        Arrays.sort(nums);
        int sln = nums.length - 2;
        for (int i = nums.length - 2; nums[i] == nums[nums.length - 1]; --i) {
            sln = i;
            if (i == 0)
                break;
        }
        int res = -1;
        if (nums[nums.length - 1] >= 2 * nums[sln]){
            // 不用 binarySearch 方法:需要首先进行排序,这里会打乱原有下标
            // return Arrays.binarySearch(bNums, nums[nums.length - 1]);
            for (int i = 0; i < bNums.length; ++i){
                if (bNums[i] == nums[nums.length - 1]){
                    res = i;
                    break;
                }
            }
        }
        return res;
    }
}

开头照样是两个直接判断,也是防止后面 length - 2 取值的时候溢出。
其中 binarySearch 这个方法,使用之前需要先排序,所以只能手动查找了。

用自带的方法有点讨巧,复杂度是O(n),用时很少:2ms。

但是定睛一看:

执行用时:2 ms ,在所有Java提交中击败了 14.90% 的用户

纳尼?排名这么后。看来排序之后再判断,使不得。

开始探究

其实还是一开始偷懒了,如果不排序,而是直接在遍历的时候确定最大元素和第二大元素,就会更快一点。
原因就是,排序了之后也还要遍历两次,不慢才怪 🤣

重新来,减少遍历次数:

class Solution {
    public int dominantIndex(int[] nums) {
        if (nums.length == 1)
            return 0;
        if (nums.length == 2)
            return nums[0] >= nums[1] ? 0 : 1;
        int[] bNums = Arrays.copyOf(nums, nums.length);
        Arrays.sort(nums);
        int res = -1;
        if(nums[nums.length - 1] >= 2 * nums[nums.length -2]){
            for (int i = 0; i < bNums.length; ++i){
                if (bNums[i] == nums[nums.length - 1])
                    res = i;
            }
        }
        return res;
    }
}

这次只遍历一遍,应该会快点了吧——执行——诶,怎么还是 2 ms ?
看来问题主要出在sort排序上。单纯的循环,多一遍既不会影响时间复杂度,也不怎么耗时(当然是数据量少的情况下)。
而且排序还会导致后面找原先位置的时候,得复制保留一个原样数组。这也增加了空间复杂度。

去掉排序试一下,直接通过遍历取两个值:

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

一次循环,解决问题。
就是一定要看清题目的测试用例范围,不然在大于等于以及边界这些细节上,会白白耗费精力。

提交结果:

执行用时:1 ms ,在所有Java提交中击败了 69.41% 的用户

嗯?难道还有更快的方法?

快枪手方案

名字是我瞎起的,因为实在是太快了哈哈哈。

class Solution {
    public int dominantIndex(int[] nums) {
        int length = nums.length;
        if (length == 1)
            return 0;
        if (length == 2)
            return nums[0] >= nums[1] ? 0 : 1;
        int max = 0;
        for (int i = 0; i < length; ++i){
            if(nums[i] > nums[max])
                max = i;
        }
        for (int i = 0; i < length; ++i){
            if(i != max && 2 * nums[i] > nums[max])
                return -1;
        }
        return max;
    }
}

来自官方解答。嗯…看起来简洁易懂多了。
而且在第二个判断时用了反向思维。有不满足条件的就直接返回 -1 ,否则循环完毕后返回 max 。
非常精妙,尤其比起第一个复杂的做法时。

提交效果自然是最棒的:

最终结果

结语

总结一下:

  • 同时间复杂度下,循环次数多不一定速度就慢,还要看你在循环里的操作。
  • 数组取长度同样有消耗,如果需要多次使用,最好用个临时变量储存起来,拿一小点空间换时间。
  • 有时候反向判断可能是更直接更好的方法。

今天顺带把博客的主题升级了一下,体验了一次 merge upstream conflict 的感觉,手动解决所有冲突(自己魔改了过主题的代码)后,果然——跑不起来了。最后还是顺着报错提示和 issue 找到了问题所在,更改了错误的配置项。

开始做题阻力很大,几个小时才能彻底搞懂一道,手写通过。但是也有好消息,比如又有人想买我的源码2333,还有 天意 继创造者日报推荐后,今天又被 少数派 文章推荐啦 😊虽然是个小玩意,但用心做的东西能被别人体会称赞,还是很有成就感滴。

最后想说的是,不要因为怕麻烦或担心失败就拖着不动,如果是应该做的事情,努力做好就总能向成功更进一步。