循环数组中相邻元素的最小绝对差
原文: https://www.geeksforgeeks.org/minimum-absolute-difference-adjacent-elements-circular-array/
给定n
个整数,它们形成一个圆。 找到任何相邻对的最小绝对值。 如果有许多最佳解决方案,请输出其中任何一个。
注意:它们在圈子中。
例子:
Input : arr[] = {10, 12, 13, 15, 10}
Output : 0
Explanation: |10 - 10| = 0 which is the
minimum possible.
Input : arr[] = {10, 20, 30, 40}
Output : 10
Explanation: |10 - 20| = 10 which is the
minimum, 2 3 or 3 4 can be the answers also.
首先考虑最小值是第一和第二元素。 从第二个元素遍历到最后一个。 检查每个相邻对的差异并存储最小值。 当到达最后一个元素时,检查其与第一个元素的区别。
下面是上述方法的实现。
C++
// C++ program to find maximum difference
// between adjacent elements in a circular array.
#include <bits/stdc++.h>
using namespace std;
void minAdjDifference(int arr[], int n)
{
if (n < 2)
return;
// Checking normal adjacent elements
int res = abs(arr[1] - arr[0]);
for (int i = 2; i < n; i++)
res = min(res, abs(arr[i] - arr[i - 1]));
// Checking circular link
res = min(res, abs(arr[n - 1] - arr[0]));
cout << "Min Difference = " << res;
}
// driver program to check the above function
int main()
{
int a[] = { 10, 12, 13, 15, 10 };
int n = sizeof(a) / sizeof(a[0]);
minAdjDifference(a, n);
return 0;
}
Java
// Java program to find maximum difference
// between adjacent elements in a circular
// array.
class GFG {
static void minAdjDifference(int arr[], int n)
{
if (n < 2)
return;
// Checking normal adjacent elements
int res = Math.abs(arr[1] - arr[0]);
for (int i = 2; i < n; i++)
res = Math.min(res, Math.abs(arr[i] - arr[i - 1]));
// Checking circular link
res = Math.min(res, Math.abs(arr[n - 1] - arr[0]));
System.out.print("Min Difference = " + res);
}
// driver code
public static void main(String arg[])
{
int a[] = { 10, 12, 13, 15, 10 };
int n = a.length;
minAdjDifference(a, n);
}
}
// This code is contributed by Anant Agarwal
// and improved by Anuj Sharma.
Python3
# Python3 program to find maximum
# difference between adjacent
# elements in a circular array.
def minAdjDifference(arr, n):
if (n < 2): return
# Checking normal adjacent elements
res = abs(arr[1] - arr[0])
for i in range(2, n):
res = min(res, abs(arr[i] - arr[i - 1]))
# Checking circular link
res = min(res, abs(arr[n - 1] - arr[0]))
print("Min Difference = ", res)
# Driver Code
a = [10, 12, 13, 15, 10]
n = len(a)
minAdjDifference(a, n)
# This code is contributed by Anant Agarwal
# and improved by Anuj Sharma.
C#
// C# program to find maximum difference
// between adjacent elements in a circular array.
using System;
class GFG {
static void minAdjDifference(int[] arr, int n)
{
if (n < 2)
return;
// Checking normal adjacent elements
int res = Math.Abs(arr[1] - arr[0]);
for (int i = 2; i < n; i++)
res = Math.Min(res, Math.Abs(arr[i] - arr[i - 1]));
// Checking circular link
res = Math.Min(res, Math.Abs(arr[n - 1] - arr[0]));
Console.Write("Min Difference = " + res);
}
// driver code
public static void Main()
{
int[] a = { 10, 12, 13, 15, 10 };
int n = a.Length;
minAdjDifference(a, n);
}
}
// This code is contributed by Anant Agarwal
// and improved by Anuj Sharma.
PHP
<?php
// PHP program to find maximum
// difference between adjacent
// elements in a circular array.
function minAdjDifference($arr, $n)
{
if ($n < 2)
return;
// Checking normal
// adjacent elements
$res = abs($arr[1] - $arr[0]);
for ($i = 2; $i < $n; $i++)
$res = min($res,
abs($arr[$i] -
$arr[$i - 1]));
// Checking circular link
$res = min($res, abs($arr[$n - 1] -
$arr[0]));
echo "Min Difference = ", $res;
}
// Driver Code
$a = array(10, 12, 13, 15, 10);
$n = count($a);
minAdjDifference($a, $n);
//This code is contributed by anuj_67
//and improved by Anuj Sharma.
?>
Output:
Min Difference = 0
时间复杂度:O(n)
。
版权属于:月萌API www.moonapi.com,转载请注明出处