当前位置:网站首页>1855. Maximum distance of subscript alignment
1855. Maximum distance of subscript alignment
2022-07-06 16:08:00 【mrbone9】
Address :
Power button https://leetcode-cn.com/problems/maximum-distance-between-a-pair-of-values/
subject :
Here are two for you Non-increasing Array of integers for nums1 and nums2 , Array subscripts are from 0 Start Count .
Subscript pair (i, j) in 0 <= i < nums1.length And 0 <= j < nums2.length . If the subscript pair satisfies both i <= j And nums1[i] <= nums2[j] , Call it It works Subscript pair , The subscript is right distance by j - i .
Back to all It works Subscript pair (i, j) Medium Maximum distance . If there is no valid subscript pair , return 0 .
An array arr , If each 1 <= i < arr.length Both arr[i-1] >= arr[i] establish , So the array is a Non-increasing Array .
Example 1:
Input :nums1 = [55,30,5,4,2], nums2 = [100,20,10,10,5] Output :2 explain : The valid subscript pair is (0,0), (2,2), (2,3), (2,4), (3,3), (3,4) and (4,4) . The maximum distance is 2 , Corresponding subscript pair (2,4) . |
Example 2:
Input :nums1 = [2,2,2], nums2 = [10,10,1] Output :1 explain : The valid subscript pair is (0,0), (0,1) and (1,1) . The maximum distance is 1 , Corresponding subscript pair (0,1) . |
Example 3:
Input :nums1 = [30,29,19,5], nums2 = [25,25,25,25,25] Output :2 explain : The valid subscript pair is (2,2), (2,3), (2,4), (3,3) and (3,4) . The maximum distance is 2 , Corresponding subscript pair (2,4) . |
Example 4:
Input :nums1 = [5,4], nums2 = [3,2] Output :0 explain : There is no valid subscript pair , So back 0 . |
Tips :
1 <= nums1.length <= 105 1 <= nums2.length <= 105 1 <= nums1[i], nums2[j] <= 105 nums1 and nums2 All are Non-increasing Array |
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/maximum-distance-between-a-pair-of-values
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Ideas :
For a non increasing array , It means that the value of array elements is decreasing
Traverse the array according to the meaning of the question 1 Every element of , And array 2 Compare the elements of , Find the maximum distance
To reduce the number of comparisons , From the array 2 Compare the last element of , This is the longest distance , If it doesn't , Then compare the second
Such a violent solution is bound to timeout , The code is posted below
Since violence doesn't work, we have to think of other ways
Because it is a comparative distance , Array values are not directly related to distance , Therefore, two sets of data cannot be deduced , We can only compare
With i As Array 1 The subscript ,j As Array 2 The subscript
i from 0 Start , Initially found step ( Longest distance ) zero
[i] In the array 2 Look for the biggest place to exist , The last one [i] <= [j], Set up step = j - i
first i When the element is complete , We found the step size
The next element i+1 The element benchmarking is j+1 The location of ,
There may be [i+1] == [j+1] , A distance of 0, It won't be longer than the last time , So don't consider
May also be [i+1] <= [j+n],j After a certain step n In the back . This address is where we start to compare , therefore
The step length we found in the first step is used as a new starting point , If a new starting point [j] > [i], We will continue to try j Move back to find a new step
Such a calculation step can effectively reduce the number of comparisons
Method 1 、BF
int maxDistance(int* nums1, int nums1Size, int* nums2, int nums2Size){
int i, j;
int max = 0;
for(i=0; i<nums1Size; i++)
{
for(j=nums2Size-1; j>=0; j--)
{
if(nums1[i] <= nums2[j])
{
if(max < (j-i) )
max = j-i;
break;
}
}
}
return max;
}
Method 2 、 Step comparison
int maxDistance(int* nums1, int nums1Size, int* nums2, int nums2Size){
int i, j;
int step = 0;
for(i=0; i<nums1Size; i++)
{
if(i+step < nums2Size && nums1[i] > nums2[i+step])
continue;
for(j=i+step; j<nums2Size; j++)
{
//printf("2..nums1[%d]=%d, nums2[%d]=%d\n", i, nums1[i], j, nums2[j]);
if(nums1[i] <= nums2[j])
{
step = j-i;
}
else
break;
}
}
return step;
}
边栏推荐
- Web based photo digital printing website
- [exercise-7] crossover answers
- Analyse du format protobuf du rideau en temps réel et du rideau historique de la station B
- Luogu P1102 A-B number pair (dichotomy, map, double pointer)
- Research Report on surgical fluid treatment industry - market status analysis and development prospect prediction
- Research Report of cylindrical grinder industry - market status analysis and development prospect forecast
- 信息安全-安全专业名称|CVE|RCE|POC|VUL|0DAY
- 【练习-8】(Uva 246)10-20-30==模拟
- Penetration test (2) -- penetration test system, target, GoogleHacking, Kali tool
- Penetration test (3) -- Metasploit framework (MSF)
猜你喜欢
Penetration test 2 --- XSS, CSRF, file upload, file inclusion, deserialization vulnerability
b站 实时弹幕和历史弹幕 Protobuf 格式解析
Ball Dropping
Penetration test (8) -- official document of burp Suite Pro
渗透测试 ( 8 ) --- Burp Suite Pro 官方文档
C language must memorize code Encyclopedia
Information security - threat detection - Flink broadcast stream broadcaststate dual stream merging application in filtering security logs
Nodejs+vue网上鲜花店销售信息系统express+mysql
frida hook so层、protobuf 数据解析
Web based photo digital printing website
随机推荐
Opencv learning log 15 count the number of solder joints and output
Penetration test (7) -- vulnerability scanning tool Nessus
Understand what is a programming language in a popular way
树莓派4B安装opencv3.4.0
信息安全-安全编排自动化与响应 (SOAR) 技术解析
[exercise-4] (UVA 11988) broken keyboard = = (linked list)
MySQL grants the user the operation permission of the specified content
Information security - security professional name | CVE | rce | POC | Vul | 0day
Auto.js入门
Opencv learning log 16 paperclip count
双向链表—全部操作
The concept of C language array
Common configuration files of SSM framework
b站 实时弹幕和历史弹幕 Protobuf 格式解析
渗透测试 ( 4 ) --- Meterpreter 命令详解
【练习-11】4 Values whose Sum is 0(和为0的4个值)
Write web games in C language
MySQL import database error [err] 1273 - unknown collation: 'utf8mb4_ 0900_ ai_ ci’
China potato slicer market trend report, technical dynamic innovation and market forecast
【练习-5】(Uva 839)Not so Mobile(天平)