LargestNumberAtLeastTwiceOfOthers [source code]

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

    public static void main(String[] args) {
        LargestNumberAtLeastTwiceOfOthers.Solution tester = new LargestNumberAtLeastTwiceOfOthers.Solution();
        int[][] inputs = {
            {3, 6, 1, 0}, {1},
            {1, 2, 3, 4}, {-1},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            int[] nums = inputs[2 * i];
            int ans = inputs[2 * i + 1][0];
            System.out.println (Printer.separator ());
            int output = tester.dominantIndex (nums);
            System.out.printf ("%s -> %s, expected: %d\n",
                Printer.array (nums), Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
            );
        }
    }
}

题目意思还是很清楚的, 笨办法的思路也很简单, 两个pass就行了; 不过既然是Google的题目, 没有一点弯弯绕是不可能的. 这个题目最后面试的时候肯定是追求让你提出不需要2pass的做法;

暂时没有什么好的思路, 那么就从笔算笨办法开始, 在细节当中寻找优化空间;

当然, array的题目, 大多数时候都可以用sort来降低难度, 不过这题笨办法本身就可以做到O(N), 你sort之后还升高了复杂度, 肯定不行;

这个题目给了一个非常方便的domain, 感觉像是鼓励你用value as index的技巧? 那么这个array应该是用来记录什么的呢?

想了半天没有想到什么特别好的办法, 只想到一个1pass的解法, 速度是19ms (NA). 注意, 维护max2这个是一个非常基本的题型了, 这个时候应该很熟悉了;

注意, body里面的2和3两个branch是可以合并的, 不过我还是摆在这里提醒一下自己, 另外一方面就是, 判断相等在有些特定的题目里面, 往往还正好是一个关键步骤;

editorial做法, 2pass:

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

题目比较新, discussion和submission都没有什么新货;

Problem Description

In a given integer array nums, there is always exactly one largest element.

Find whether the largest element in the array is at least twice as much as every other number in the array.

If it is, return the index of the largest element, otherwise return -1.

Example 1:

Input: nums = [3, 6, 1, 0]  
Output: 1  
Explanation: 6 is the largest integer, and for every other number in the array x,  
6 is more than twice as big as x.  The index of value 6 is 1, so we return 1.

Example 2:

Input: nums = [1, 2, 3, 4]  
Output: -1  
Explanation: 4 isn't at least as big as twice the value of 3, so we return -1.

Note:

• nums will have a length in the range [1, 50].
• Every nums[i] will be an integer in the range [0, 99].

Difficulty:Easy
Total Accepted:5.5K
Total Submissions:12K
Contributor:TopCoder111
Companies
google
Related Topics
array

Hide Hint 1

Scan through the array to find the unique largest element m, keeping track of it's index maxIndex. Scan through the array again. If we find some x != m with m < 2*x, we should return -1. Otherwise, we should return maxIndex.