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! πͺπͺπͺ