C语言 如何找到最小值在数组非常大的大小和也大的值在数组中

anauzrmj  于 2022-12-17  发布在  其他
关注(0)|答案(2)|浏览(81)

我试图找到一个数组的最小值,然后检查最小值的频率,但问题是,如果数组的大小和它存储的值很大,我的代码不工作。

1〈A[i]〈10^9
1〈N〈10^5****1〈T〈10

这里A是数组,N是数组大小,T是测试用例的数量

c程序

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

查找最小值

int findMin(int A[], int N)
{
    int min;
    int i;
    if(N>2)
    {
        for(i=0;i<N;i++)
        {
            if( A[i]<=A[i+1])
            {
                min = A[i];
                int temp = A[i];
                A[i]=A[i+1];
                A[i+1] = temp;
            }
        }
    }
    else
    {
        min = A[0];
    }

    return freq(min,A,N);

}

数组中最小值的频率

int freq(int min, int A[], int N)
{
    int i,count=0;
    for(i=0;i<N;i++)
    {
        if(min == A[i])
        {
            count++;
        }
    }

    return count%2;
}

主文件()

int main()
{

    int *A,N;
    int i,T;
    scanf("%d",&T);
    while(T>0)
    {
        scanf("%d",&N);
        A = (int *)calloc(N,sizeof(int));
        for(i=0;i<N;i++)
        {
            scanf("%d",&A[i]);
        }
        if(findMin(A,N) == 1)
        {
            printf("Lucky\n");
        }
        else
        {
            printf("Unlucky\n");
        }

        T--;
   }
    return 0;
}

[编辑]编码目标
count%2用于检查频率是奇数还是偶数

wpx232ag

wpx232ag1#

如果你对寻找数组中的最小值感兴趣,你对“频率”感兴趣,你定义它为最小值的计数是奇数还是偶数,也许这就是你需要的?

int findMinAndFreq(int A[], int N){
   if(N == 0){
      printf("Array is empty");
      return 0;
   }
   if(N == 1){
      return 1;
   }

   int min = A[0];
   int count = 1;
   for(int i = 1; i<N; i++){
      if(A[i] == min){
         count++;
      }
      if(A[i] < min){
         min = A[i];
         count = 1;
      }
   }
   return count%2;
}
u1ehiz5o

u1ehiz5o2#

问题就在这里:

for(i=0;i<N;i++)
    {
        if( A[i]<=A[i+1])
        {
        ...

在循环的最后一次迭代中,当iN-1时,A[i+i]是超出数组末尾的一个元素。超出数组末尾的阅读调用undefined behavior
你也将列表中最小的元素上移了,因为你已经跟踪了最小值,所以不需要修改列表。
与其检查相邻的元素,不如将当前元素与最小值进行比较。您也不需要到处移动元素,也不需要为数组1添加特殊情况:

int findMin(int A[], int N)
{
    int min;
    int i;

    min = A[0];
    for(i=0;i<N;i++)
    {
        if(A[i] < min)
        {
            min = A[i];
        }
    }

    return freq(min,A,N);
}

您也不需要循环遍历列表两次,因为您可以在遍历列表时计算看到min的次数。

相关问题