返回给定数组中的最小唯一值-C语言 [英] Return the smallest unique value in a given array - C Language

问题描述

我不确定要在此处应用哪种算法.我的想法是，我应该首先找到所有唯一值，然后再从那里获取最小值.但是，我不确定如何实现这一点.我正在尝试用C语言做到这一点.

I'm not sure what sort of algorithm to apply here. My thoughts are that I should go about finding all the unique values first and then from there I should grab the minimum. However, I'm not sure how to implement this. I'm trying to do this in C.

唯一的限制是我只能使用 #include< stdio.h> #include< string.h> .

The only constraints are that I can only use #include <stdio.h> #include <string.h>.

推荐答案

使用您在问题中提出的算法(即首先找到所有唯一值，然后找到最低值)，可能的实现如下所示:

Using the algorithm you propose in your question (i.e. to first find all unique values and then find the lowest one), a possible implementation looks like this:

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

// NOTE: The second parameter array_size specifies the number of
// int elements in the array, NOT the size of the array in bytes.
int find_unique_min( int *array_start, int array_size )
{
    int *unique_values; //pointer to the dynamically allocated array with the unique values
    int num_unique_values; //number of values in the secondary array
    int minimum; //smallest unique value found so far
    int i, j; //loop counter variables

    // We don't know yet how many unique values there will be, so we don't know
    // how big the secondary array which holds the unique values must be.
    // However, in the worst case, every value is unique, which means that in
    // the worst case, the secondary array must have the same size as the 
    // primary array. Therefore, we make it the same size.
    unique_values = malloc( array_size * sizeof( int ) );
    if ( unique_values == NULL ) {
        fprintf( stderr, "Memory allocation error\n" );
        return -1;
    }

    // This variable specifies the number of valid elements in the
    // secondary array, which must be set to zero for now.
    num_unique_values = 0;

    //fill secondary array with unique values
    for ( i = 0; i < array_size; i++ )
    {
        // compare the current array element with all other elements
        for ( j = 0; j < array_size; j++ )
        {
            // Since the comparison will say the values are identical when
            // comparing an element with itself, we must also check whether we
            // are comparing the element with itself.
            if ( array_start[i] == array_start[j] && i != j ) goto not_unique;
        }

        // We have now determined that the current array element is unique,
        // so we add it to the secondary array.
        unique_values[num_unique_values++] = array_start[i];

not_unique:
        continue;
    }

    //return -1 if no unique values were found
    if ( num_unique_values == 0 )
    {
        free( unique_values );
        return -1;
    }

    //find lowest value in secondary array and return it
    minimum = INT_MAX;
    for ( i = 0; i < num_unique_values; i++ )
    {
        if ( unique_values[i] < minimum ) minimum = unique_values[i];
    }

    free( unique_values );

    return minimum;
}

我添加< stdlib.h> (似乎是您的分配规则所禁止的)的唯一原因是因为我需要为辅助阵列动态分配内存以存储唯一价值观.如果改为分配静态数组，则可以摆脱该include指令.但是，对于静态数组，必须在编译时知道最大唯一数(以便确定要分配多少内存).

The only reason I included <stdlib.h> (which seems to be forbidden by the rules of your assignment) was because I needed to dynamically allocate memory for the secondary array to store the unique values. If you allocate a static array instead, you can get rid of that include directive. However, for a static array, the maximum number of unique numbers must be known at compile time (in order to determine how much memory to allocate).

或者，您可以将两个步骤(查找唯一值和找到最小值)组合为一个步骤.这样，您就不需要辅助阵列，也不需要(动态地)为其分配内存.在这种情况下，您也不必 #include< stdlib.h> .

Alternatively, you can combine both steps (finding the unique values and finding the minimum value) into one. That way, you don't need a secondary array and you also don't need to (dynamically) allocate memory for it. In that case, you also don't have to #include <stdlib.h>.

可以使用以下算法将两个步骤组合在一起:

Combining both steps could be done using the following algorithm:

您可以从头到尾遍历整个数组(循环)，并始终记住(在变量中)到目前为止所遇到的最低唯一值.每当遇到较低的值时，便将此值与数组的所有其他元素进行比较，以确定其是否唯一.如果确实是唯一的，则请记住该新值，而不是前一个值，并继续处理数组的其余部分.在循环的最后，您只需返回包含所遇到的最小唯一值的变量的值即可.

You can just go through the whole array from start to end (in a loop) and always remember (in a variable) the lowest unique value you have encountered so far. Whenever you encounter a lower value, you compare this value with all other elements of the array in order to determine whether it is unique. If it indeed is unique, you remember this new value instead of the previous one and continue with the rest of the array. At the end of the loop, you simply return the value of the variable which contains the lowest unique value you encountered.

此算法的实现如下所示:

An implementation of this algorithm could look like this:

#include <stdio.h>

#ifndef INT_MAX
#define INT_MAX 2147483647
#endif

// NOTE: The second parameter array_size specifies the number of
// int elements in the array, NOT the size of the array in bytes.
int find_unique_min( int *array_start, int array_size )
{
    int minimum; //smallest unique value found so far
    int i, j; //loop counter variables

    minimum = INT_MAX;

    for ( i = 0; i < array_size; i++ )
    {
        if ( array_start[i] < minimum )
        {
            // test if current element value is unique
            for ( j = 0; j < array_size; j++ )
            {
                if ( array_start[i] == array_start[j] && i != j ) goto not_unique;
            }

            minimum = array_start[i];
        }
not_unique:
        continue;
    }

    //if no unique value was found, return -1
    if ( minimum == INT_MAX ) return -1;

    return minimum;
}

请注意，通常不应手动定义 INT_MAX .我这样做的唯一原因是由于该问题中提到的限制导致无法使用 #include< stdlib.h> .

Please note that normally, INT_MAX should not be defined manually. The only reason I did this is because of the restriction mentioned in the question which prevented #include <stdlib.h> from being used.

这篇关于返回给定数组中的最小唯一值-C语言的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！