所有阵列对的最大模，其中arr[i]>=arr[j]-yiteyi-C++库

给定一个由n个整数组成的数组。求arr[i]mod arr[j]的最大值，其中arr[i]>=arr[j]和1<=i，j<=n 例如：

null

Input: arr[] = {3, 4, 7}Output: 3Explanation:There are 3 pairs which satisfies arr[i] >= arr[j] are:-4, 3 => 4 % 3 = 17, 3 => 7 % 3 = 17, 4 => 7 % 4 = 3Hence Maximum value among all is 3.Input: arr[] = {3, 7, 4, 11}Output: 4Input: arr[] = {4, 4, 4}Output: 0

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

A. 天真的方法 就是运行两个嵌套的for循环，并在取它们的模后选择每个可能对的最大值。这种方法的时间复杂度为O（n ^2. )这对于n的大值是不够的。一 有效的方法（当元素来自小范围时） 是使用排序和二进制搜索的方法。首先，我们将对数组进行排序，以便能够对其应用二进制搜索。因为我们需要使arr[i]mod arr[j]的值最大化，所以我们迭代从2*arr[j]到M+arr[j]范围内的每个x（这样的x可以被arr[j]整除），其中M是序列的最大值。对于x的每个值，我们需要找到arr[i]的最大值，使得arr[i] 通过这样做，我们将确保我们只选择了那些将给出最大值arr[i]mod arr[j]的arr[i]值。之后，我们只需要对arr[j]的其他值重复上述过程，并通过值a[i]mod arr[j]更新答案。例如：-

If arr[] = {4, 6, 7, 8, 10, 12, 15} then forfirst element, i.e., arr[j] = 4 we iteratethrough x = {8, 12, 16}. Therefore for each value of x, a[i] will be:-x = 8, arr[i] = 7 (7 < 8)       ans = 7 mod 4 = 3 x = 12, arr[i] = 10 (10 < 12)       ans = 10 mod 4 = 2 (Since 2 < 3,                                 No update)x = 16, arr[i] = 15 (15 < 16)       ans  = 15 mod 4 = 3 (Since 3 == 3,                          No need to update)

C++

                         // C++ program to find Maximum modulo value                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         int                                     maxModValue(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 int                                     ans = 0;                       
                                                 // Sort the array[] by using inbuilt sort function                       
                                                 sort(arr, arr + n);                       
           
                                                 for                                     (                                     int                                     j = n - 2; j >= 0; --j) {                       
                                                 // Break loop if answer is greater or equals to                       
                                                 // the arr[j] as any number modulo with arr[j]                       
                                                 // can only give maximum value up-to arr[j]-1                       
                                                 if                                     (ans >= arr[j])                       
                                                 break                                     ;                       
           
                                                 // If both elements are same then skip the next                       
                                                 // loop as it would be worthless to repeat the                       
                                                 // rest process for same value                       
                                                 if                                     (arr[j] == arr[j + 1])                       
                                                 continue                                     ;                       
           
                                                 for                                     (                                     int                                     i = 2 * arr[j]; i <= arr[n - 1] + arr[j]; i += arr[j]) {                       
                                                 // Fetch the index which is greater than or                       
                                                 // equals to arr[i] by using binary search                       
                                                 // inbuilt lower_bound() function of C++                       
                                                 int                                     ind = lower_bound(arr, arr + n, i) - arr;                       
           
                                                 // Update the answer                       
                                                 ans = max(ans, arr[ind - 1] % arr[j]);                       
                                                 }                       
                                                 }                       
                                                 return                                     ans;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 3, 4, 5, 9, 11 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 cout << maxModValue(arr, n);                       
                         }                       

JAVA

                         // Java program to find Maximum modulo value                       
           
                         import                                     java.util.Arrays;                       
           
                         class                                     Test {                       
                                                 static                                     int                                     maxModValue(                                     int                                     arr[],                                     int                                     n)                       
                                                 {                       
                                                 int                                     ans =                                     0                                     ;                       
           
                                                 // Sort the array[] by using inbuilt sort function                       
                                                 Arrays.sort(arr);                       
           
                                                 for                                     (                                     int                                     j = n -                                     2                                     ; j >=                                     0                                     ; --j) {                       
                                                 // Break loop if answer is greater or equals to                       
                                                 // the arr[j] as any number modulo with arr[j]                       
                                                 // can only give maximum value up-to arr[j]-1                       
                                                 if                                     (ans >= arr[j])                       
                                                 break                                     ;                       
           
                                                 // If both elements are same then skip the next                       
                                                 // loop as it would be worthless to repeat the                       
                                                 // rest process for same value                       
                                                 if                                     (arr[j] == arr[j +                                     1                                     ])                       
                                                 continue                                     ;                       
           
                                                 for                                     (                                     int                                     i =                                     2                                     * arr[j]; i <= arr[n -                                     1                                     ] + arr[j]; i += arr[j]) {                       
                                                 // Fetch the index which is greater than or                       
                                                 // equals to arr[i] by using binary search                       
           
                                                 int                                     ind = Arrays.binarySearch(arr, i);                       
           
                                                 if                                     (ind <                                     0                                     )                       
                                                 ind = Math.abs(ind +                                     1                                     );                       
           
                                                 else                                     {                       
                                                 while                                     (arr[ind] == i) {                       
                                                 ind--;                       
           
                                                 if                                     (ind ==                                     0                                     ) {                       
                                                 ind = -                                     1                                     ;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
                                                 ind++;                       
                                                 }                       
           
                                                 // Update the answer                       
                                                 ans = Math.max(ans, arr[ind -                                     1                                     ] % arr[j]);                       
                                                 }                       
                                                 }                       
                                                 return                                     ans;                       
                                                 }                       
           
                                                 // Driver method                       
                                                 public                                     static                                     void                                     main(String args[])                       
                                                 {                       
                                                 int                                     arr[] = {                                     3                                     ,                                     4                                     ,                                     5                                     ,                                     9                                     ,                                     11                                     };                       
                                                 System.out.println(maxModValue(arr, arr.length));                       
                                                 }                       
                         }                       

Python3

                         # Python3 program to find Maximum modulo value                       
           
                         def                                     maxModValue(arr, n):                       
           
                                                 ans                                     =                                     0                       
                                   
                                                 # Sort the array[] by using inbuilt                       
                                                 # sort function                       
                                                 arr                                     =                                     sorted                                     (arr)                       
           
                                                 for                                     j                                     in                                     range                                     (n                                     -                                     2                                     ,                                     -                                     1                                     ,                                     -                                     1                                     ):                       
                                   
                                                 # Break loop if answer is greater or equals to                       
                                                 # the arr[j] as any number modulo with arr[j]                       
                                                 # can only give maximum value up-to arr[j]-1                       
                                                 if                                     (ans >                                     =                                     arr[j]):                       
                                                 break                       
           
                                                 # If both elements are same then skip the next                       
                                                 # loop as it would be worthless to repeat the                       
                                                 # rest process for same value                       
                                                 if                                     (arr[j]                                     =                                     =                                     arr[j                                     +                                     1                                     ]) :                       
                                                 continue                       
                                                 i                                     =                                     2                                     *                                     arr[j]                       
                                                 while                                     (i <                                     =                                     arr[n                                     -                                     1                                     ]                                     +                                     arr[j]):                       
                                   
                                                 # Fetch the index which is greater than or                       
                                                 # equals to arr[i] by using binary search                       
                                                 # inbuilt lower_bound() function of C++                       
                                                 ind                                     =                                     0                       
                                                 for                                     k                                     in                                     arr:                       
                                                 if                                     k >                                     =                                     i:                       
                                                 ind                                     =                                     arr.index(k)                       
           
                                                 # Update the answer                       
                                                 ans                                     =                                     max                                     (ans, arr[ind                                     -                                     1                                     ]                                     %                                     arr[j])                       
                                                 i                                     +                                     =                                     arr[j]                       
           
                                                 return                                     ans                       
           
                         # Driver Code                       
                         arr                                     =                                     [                                     3                                     ,                                     4                                     ,                                     5                                     ,                                     9                                     ,                                     11                                     ]                       
                         n                                     =                                     5                       
                         print                                     (maxModValue(arr, n))                       
           
                         # This code is contributed by                       
                         # Shubham Singh(SHUBHAMSINGH10)                       

C#

                         // C# program to find Maximum modulo value                       
                         using                                     System;                       
           
                         public                                     class                                     GFG {                       
                                   
                                                 static                                     int                                     maxModValue(                                     int                                     [] arr,                                     int                                     n)                       
                                                 {                       
                                   
                                                 int                                     ans = 0;                       
           
                                                 // Sort the array[] by using inbuilt                       
                                                 // sort function                       
                                                 Array.Sort(arr);                       
           
                                                 for                                     (                                     int                                     j = n - 2; j >= 0; --j)                       
                                                 {                       
                                   
                                                 // Break loop if answer is greater                       
                                                 // or equals to the arr[j] as any                       
                                                 // number modulo with arr[j] can                       
                                                 // only give maximum value up-to                       
                                                 // arr[j]-1                       
                                                 if                                     (ans >= arr[j])                       
                                                 break                                     ;                       
           
                                                 // If both elements are same then                       
                                                 // skip the next loop as it would                       
                                                 // be worthless to repeat the                       
                                                 // rest process for same value                       
                                                 if                                     (arr[j] == arr[j + 1])                       
                                                 continue                                     ;                       
           
                                                 for                                     (                                     int                                     i = 2 * arr[j];                       
                                                 i <= arr[n - 1] + arr[j];                       
                                                 i += arr[j])                       
                                                 {                       
                                   
                                                 // Fetch the index which is                       
                                                 // greater than or equals to                       
                                                 // arr[i] by using binary search                       
           
                                                 int                                     ind = Array.BinarySearch(arr, i);                       
           
                                                 if                                     (ind < 0)                       
                                                 ind = Math.Abs(ind + 1);                       
           
                                                 else                                     {                       
                                                 while                                     (arr[ind] == i) {                       
                                                 ind--;                       
           
                                                 if                                     (ind == 0) {                       
                                                 ind = -1;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
                                                 ind++;                       
                                                 }                       
           
                                                 // Update the answer                       
                                                 ans = Math.Max(ans, arr[ind - 1]                       
                                                 % arr[j]);                       
                                                 }                       
                                                 }                       
                                   
                                                 return                                     ans;                       
                                                 }                       
           
                                                 // Driver method                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                   
                                                 int                                     [] arr = { 3, 4, 5, 9, 11 };                       
                                   
                                                 Console.WriteLine(                       
                                                 maxModValue(arr, arr.Length));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Sam007.                       

Javascript

                         <script>                       
           
                         // JavaScript program to find Maximum modulo value                       
           
           
                         function                                     maxModValue(arr, n) {                       
                                                 let ans = 0;                       
           
                                                 // Sort the array[] by using inbuilt sort function                       
                                                 arr.sort((a, b) => a - b);                       
           
                                                 for                                     (let j = n - 2; j >= 0; --j) {                       
                                                 // Break loop if answer is greater or equals to                       
                                                 // the arr[j] as any number modulo with arr[j]                       
                                                 // can only give maximum value up-to arr[j]-1                       
                                                 if                                     (ans >= arr[j])                       
                                                 break                                     ;                       
           
                                                 // If both elements are same then skip the next                       
                                                 // loop as it would be worthless to repeat the                       
                                                 // rest process for same value                       
                                                 if                                     (arr[j] == arr[j + 1])                       
                                                 continue                                     ;                       
           
                                                 for                                     (let i = 2 * arr[j]; i <= arr[n - 1] + arr[j];                       
                                                 i += arr[j])                       
                                                 {                       
                                                 // Fetch the index which is greater than or                       
                                                 // equals to arr[i] by using binary search                       
           
                                                 let ind = arr.indexOf(i);                       
           
                                                 if                                     (ind < 0)                       
                                                 ind = Math.abs(ind) + 1;                       
           
                                                 else                                     {                       
                                                 while                                     (arr[ind] == i) {                       
                                                 ind--;                       
           
                                                 if                                     (ind == 0) {                       
                                                 ind = -1;                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
                                                 ind++;                       
                                                 }                       
           
                                                 // Update the answer                       
                                                 ans = Math.max(ans, arr[ind - 1] % arr[j]);                       
                                                 }                       
                                                 }                       
                                                 return                                     ans;                       
                         }                       
           
                         // Driver method                       
           
                         let arr = [3, 4, 5, 9, 11];                       
                         document.write(maxModValue(arr, arr.length));                       
           
                         </script>                       

输出：

时间复杂性： O（nlog（n）+Mlog（M）），其中n是元素总数，M是所有元素的最大值。 辅助空间： O（1）本博客由 Shubham Bansal .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章