0

如果数组中的每个整数都是唯一的（不同的），我必须编写一个返回 true 的函数。因此，我尝试更正我的 for 循环/我的 if 语句，并尝试运行我编写的测试。但是，对包含多次出现的整数的字符串的测试仍然失败。我已经查看了我的代码，但我仍然找不到问题。

#include "in.h"

int in(int input[], int size)
{
   for (int i = 0; i < size - 1; i++)
   {
      for (int j = i + 1; j < size; j++)
      {
         if (input[i] == input[j])
         {
            return 0;
         }
      }
   }

   return 1;
}

这是我的测试用例：

#include "in.h"
#include "checkit.h"

void in_tests(void)
{
   int input[3] = {2, 4, 5};
   int answer;

   answer = in(input, 3);
   checkit_int(answer, 1);

   int input1[4] = {1, 3, 4, 1};
   int answer1;

   answer1 = in(input1, 4);
   checkit_int(answer, 0);
}

int main()
{
   in_tests();

   return 0;
}
4

7 回答 7

3

没有排序，一个 O(n 2 )：

j 以 i+1 开头。

int IsDiff(int array[], int count)
{
    int i,j;
    for (i=0; i<count; i++)
    {
        for (j=i+1;j<count;j++)
        {
            if (array[i] == array[j])
                return 0;
        }
    }
    return 1;
}
于 2013-05-30T02:14:13.230 回答
2

如果空间不是问题，那么我们可以使用哈希表获得 O(n) 解决方案。开始将数组的每个元素存储在哈希表中。在插入元素时，检查它是否已经存在于哈希表中（这需要 O(1) 时间。）如果元素已经存在，则立即返回 false，否则迭代直到数组末尾并返回 true。

于 2013-05-30T02:23:29.987 回答
1

实际上，这不是您的功能不起作用的原因。主要原因是因为目前您正在检查是否有任何一对 DONT 匹配，如果您想查看所有元素是否匹配，这将是很好的，但您想做相反的事情，所以您想检查相反的情况，如果有任何一对 DOES匹配。所以首先改变你的 if to be

if(input[i] == input[j]) return false;

如果一对相等，那么您知道您的测试已经失败，因此无需检查剩余的对，只需在此处返回 false 即可。

唯一要做的另一件事是整理你的循环，以便你只对每一对迭代一次并且不将一个值与它的自身进行比较。为此，将 for 循环更改为：

for(int i =0; i<size-1; i++)
   for(int j=i+1; j<size; j++)

那么如果你到达函数的末尾，这意味着没有匹配的对，所以只返回true；

于 2013-05-30T02:16:17.687 回答
0

O(n^2) 也是如此......但我添加了这个函数，使代码更易于理解......

int unique(int input[], int value,int size){
    int times=0;
    for (int i = 0; i < size; i++)
    {
        if(input[i]==value){
             times++;
             if(times==2)
                return 0;
        }
    }  
    return 1;
}

int in(int input[], int size)
{
   int x, answer;

   for (int i = 0; i < size; i++)
   {  
      if(!unique(input,input[i],size))
          return 0;
   }
   return 1;
}
于 2013-05-30T02:11:24.030 回答
0

你很接近，试试这个：

#include "in.h"

int in(int input[], int size)
{
   int answer = 1;

   for (int i = 0; i < size-1; i++)
   {  
      for (int j = i+1; j < size; j++)  //check everything above your current 
                                        //value because you have already checked 
                                        //below it.
      {
         if (input[i] == input[j])
         {
            answer = 0;                  //If any are not unique you
            break;                       //should exit immediately to save time

         }
      }
      if (answer == 0)
          break
   }
   return answer;
}
于 2013-05-30T02:14:55.827 回答
0

这是我的尝试（虽然非常简单且效率低下）：

#include <stdio.h>

int uniq_int(int arr [], int size)
{        
    int i, j;

    for (i = 0; i < size; i++) 
        for (j = i + 1; j < size; j++)
            if (arr[i] == arr[j])
                return 0;

    return 1;
}


int main()
{
    int arr [] = {1, 2, 4, 3, 5};

    (uniq_int(arr, 5)) ? printf("Unique!\n") : printf("Not...\n");
    /* the above can be written more traditionally like this:
    if (uniq_int(arr, 5) != 0)
    {
        printf("Unique!\n");
    }
    else
    {
        printf("Not...\n");
    }
    */

    return 0;
}

这会将数组的每个成员与其余成员进行比较，从第一个开始并将其与下一个进行比较，依此类推，直到内部循环结束。

然后我们再次启动外循环，但这次我们将数组的第二个元素与它后面的元素进行比较。

一旦找到匹配项，该函数就会返回，并且不需要比较其他元素。否则，外循环将一直持续到最后一个元素，一旦到达，它将退出并返回 1，这意味着每个成员都是唯一的。

它的复杂度为 O(n^2)，因为在最坏的情况下，每个成员都会对集合进行两次处理。

于 2013-05-30T02:17:36.817 回答
0

思考问题

假设你有一个这样的数组：int array[] = { 3, 1, 4, 8, 2, 6, 7, 7, 9, 6 };

如果从第一个元素开始，则需要与集合中的其余元素进行比较；所以需要将 3 与 1、4、3... 等进行比较。

如果 3 是唯一的，您现在需要转到 1 并查看其余元素，但下次您不必担心 3 ；因此，您正在考虑的值（我们称之为 V）需要是数组 [0] 到数组 [N-1] 中的每一个，其中N的大小是array（在我们的例子中为 10）；

但是如果我们想象自己在数组的中间，我们会注意到我们已经比较了前一个元素和当前元素，而前一个元素是正在考虑的值。所以我们可以忽略我们“背后”的任何元素；这意味着比较必须从每次考虑的当前值的 INDEX 开始（我们称之为 k），并将其与从 NEXT 索引开始并到达数组末尾的值进行比较；所以我们的 10 数组的伪代码看起来像这样：

int is_a_set(int array[]) 
{
   for ( k = 0; k < 10-1 ; k++ ) { /* value under consideration */
      v = array[k]; 
      for ( m = k+1 ; m < 10; m++ ) { /* compared to the remaining array starting
                                     * starting from the next element */
           if ( v == array[m] ) { /* we found a value that matches, no need to 
                                   * to continue going, we can return from this function
                                   */
                 return true; 
           }
      }
   }
   return false;
}

现在你可以使用类似的东西：

if ( is_a_set(my_array) ) {

}

您应该能够使用它来计算其余代码:-)

注意：具有唯一元素的集合称为 aset所以我将函数命名为 is_a_set

提示：将数组 (10) 的大小转换为参数或某种变量

于 2013-05-30T02:29:13.413 回答