c - 寻找一对整数之间的最小差异

Question

给定一组未排序的整数，如何找到每对具有最小差异的整数。共有 3 个示例，如下所述:

a = random.sample (range(-200,200), 5)
b = random.sample (range(-1000, 1000), 25)
c = random.sample (range(-2000, 2000), 50)

预期的输出应该是这样的:

List A = [-85, -154, -33, 192, -160]

Minimum pairs for list A:
(-160, -154)

Answer 1

捕获! :)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct Pair
{
    size_t first;
    size_t second;
};

struct Pair minimum_difference( const int a[], size_t n )
{
    struct Pair p = { 0 };

    if ( 1 < n )
    {
        p.first = 0;
        p.second = 1;

        for ( size_t i = 0; i < n - 1; i++ )
        {
            for ( size_t j = i + 1; j < n; j++ )
            {
//              printf( "%d %d %llu\n", a[i], a[j], 
//                      ( unsigned long long )abs( a[i] - a[j] ) );
                if ( ( unsigned long long )abs( a[i] - a[j] ) <
                     ( unsigned long long )abs( a[p.first] - a[p.second] ) )
                {
                    p.first  = i;
                    p.second = j;
                }                  
            }
        }
    }

    return p;
}

int main(void) 
{
    const size_t N = 5;
    const int UPPER_BOUND = 40 * N;

    int a[N];

    srand( ( unsigned int )time( NULL ) );

    for ( size_t i = 0; i < N; i++ )
    {
        a[i] = rand() % ( 2 * UPPER_BOUND ) - UPPER_BOUND;
    }

    for ( size_t i = 0; i < N; i++ ) printf( "%d ", a[i] );
    printf( "\n" );

    struct Pair p = minimum_difference( a, N );

    printf( "(%d, %d)\n", a[p.first], a[p.second] );

    return 0;
}

程序输出可能看起来很像

119 9 -193 21 -43 
(9, 21)

此prpgram仅查找差异最小的第一对。如果有几个对具有最小差异，则必须动态分配对的数组。当然功能会改变。

另一种方法是通过使用附加数组来使用排序复制算法。然后遍历这个数组计算差值。