The largest number that is at least twice the number of other numbers

HELLO, hello everyone, I am Dumb 🙈🙈🙈
Today Dumb continues to record the process of Likou brushing questions, which is included in the column algorithm 😜😜😜

This column is based on different categories of tags, and each tag is divided into three levels: Easy, Medium, and Hard 👊👊👊

All the questions in this part are from LeetCode, and the link to the original LeetCode question is marked under each question 🏃🏃🏃

OK, brothers, don’t talk nonsense and go straight to the topic, go ahead 🌞🌞🌞

A 🏠 topic description

747. Largest Number At Least Twice Other Numbers

You are given an array of integers nums in which there is always a unique largest integer

Please find the largest element in the array and check if it is at least twice every other number in the array. If yes, returns the index of the largest element, otherwise returns -1

Example 1:

enter: nums = [3,6,1,0]
Output: 1
 Explanation: 6 is the largest integer that is at least twice as large as other integers in the array.  The subscript of 6 is 1 , so 1 is returned.

Example 2:

enter: nums = [1,2,3,4]
output:-1
 Explanation: 4 is not twice as big as 3, so returns -1 . 

Example 3:

enter: nums = [1]
output: 0
 Explanation: Since no other numbers exist, the existing number 1 is assumed to be at least twice as large as the other numbers.

hint:

• 1 <= nums.length <= 50
• 0 <= nums[i] <= 100
• the largest element in nums is unique

Two 🏠Thoughts to solve the problem

2.1 🚀 Key information

The first step in solving the problem is of course to extract the key information of the title literal 😎😎😎

The question is easy to understand, find the largest element in the array and check if it is at least twice every other number in the array 🌷🌷🌷

From the title, it is easy to know that the 3 × 3 magic square must be a different number from 1 to 9 (the first time the error is solved and it is greater than 9, the review must be careful 😭😭😭)

For a 3 × 3 magic square, its central element must be 5, so when traversing the input matrix, only the central element needs to be traversed, so the loop condition is [ 1 , len - 1 )

After extracting the key information in the topic, go directly to the second stage and organize your thoughts 😃😃😃

2.2 🚀 Organize ideas

one pass method

① Traverse the array to find the maximum value Max1 and the second maximum value Max2 respectively

② If the maximum value is at least twice the next largest value, then the maximum value is at least twice the rest of the numbers, then return the subscript of the maximum value, otherwise return -1

③ In order to return the maximum value subscript, it is necessary to record the maximum value subscript while calculating the maximum value 🌸🌸🌸

After sorting out the problem-solving ideas, directly enter the third stage, and the code is realized 😃😃😃

Three 🏠 code explanation

3.1 🚀 Code implementation

According to our idea of ​​breaking the problem just now, let’s go directly to the code 👇👇👇👇

int dominantIndex(vector<int>& nums) {
    int elem1 = INT_MIN, elem2 = INT_MIN; //define maximum and second maximum
    size_t len = nums.size(), dominantIndex = 0; //Get the length of the array, define the maximum subscript

    for (size_t i = 0; i < len; ++i) { //iterate over the array
        if (nums[i] > elem1) { //If any member is greater than the maximum
            elem2 = elem1; //Assign the current maximum value to the next largest value
            elem1 = nums[i]; //The member becomes the new maximum
            dominantIndex = i; //Record the member index
        } else if (nums[i] > elem2) { //If any member is greater than the next largest value
            elem2 = nums[i]; //Assign member to next largest value
        }
    }

    return elem1 >= 2 * elem2 ? dominantIndex  : -1; //Determine whether the maximum value is more than twice the second maximum value
} 

3.2 🚀 Detailed Analysis

After reading 👀👀👀 full-annotated version of the code implementation, I believe that the general logic is capitalized OK. 😃😃😃

Then we dig out the obscure details of the above implementation 😖😖😖 to analyze it, start working directly, and walk up 👇👇👇👇

elem1 >= 2 * elem2 ? dominantIndex : -1; //Determine whether the maximum value is more than twice the second maximum value

If the maximum value is at least twice the next largest value, then the maximum value is at least twice the rest of the numbers, then return the subscript of the maximum value, otherwise return -1 🐳🐳🐳

Four 🏠 mental journey

In order to make it easier for readers to understand the blogger’s real process of brushing questions, I have restored the pure and true state at that time and recorded it in the section of mental journey. Those who are not interested can skip it directly.

There is no problem for bloggers to extract 🚀 key information in the first stage, and there is no problem with 🚀 general ideas in the second stage

Very straightforward question, the code implementation is a conventional solution, first find the maximum value and then compare in turn, obviously the above solution is better 😭😭😭, the code is as follows 👇👇👇👇

int dominantIndex(vector<int>& nums) {
    int maxElem = INT_MIN;
    size_t len = nums.size(), dominantIndex = 0;
    for (size_t i = 0; i < len; ++i) {
        if (nums[i] > maxElem) maxElem = nums[i], dominantIndex = i;
    }

    for (auto& elem : nums){
        if (elem * 2 > maxElem && elem != maxElem) return -1;
    }

    return dominantIndex;
}

Five 🏠 Conclusion

In this impetuous society, but have the patience to see this, you must be a very powerful person 👍👍👍

If you think the article is helpful, don’t forget to like + follow, your encouragement is my biggest motivation

The blogger will continue to update more high-quality content, come on! Technician! 💪💪💪