gpt4 book ai didi

c - 按升序排列多次绘制的数字。 [ C ]

转载 作者:行者123 更新时间:2023-11-30 16:38:48 26 4
gpt4 key购买 nike

我无法解决这个问题 problem

这段代码超出了时间限制,所以我认为我需要使时间复杂度更小

  #include <stdio.h> 
int main()
{
int a[100000], i, j, min, b, tmp;
scanf("%d", &b);
for (i = 0; i < b; i++)
{
scanf("%d", &a[i]);
}

for (i = 0; i < b; i++)
{
min = a[i];
tmp = i;
for (j = i; j < b-1; j++)
{
if (min > a[j])
{
min = a[j];
tmp = j;
}
}
a[tmp] = a[i];
a[i] = min;
if (i > 0)
{
if (a[i-2] != a[i] && a[i] == a[i-1]) printf("%d\n", a[i]);
}
}

return 0;
};

最佳答案

您的排序算法的复杂度为O(n^2)。对于大小为 10^5 的输入,它比 O(nlogn) 快速排序算法需要更多数量级。

这里可以使用qsort()来解决问题。

qsort(a, b, sizeof int, cmp);

其中 cmp

int cmp(const void *a, const void *b)
{
return (*(int *) a - *(int *) b);
}

排序后的算法就简单多了。

int p = a[0], ct=0;
for(size_t i = 1; i<=b-1; i++)
{
if( a[i] == a[i-1])
ct++;
else{
if( ct > 1){
// a[i-1] should be printed.
}
ct = 1;
}
}
if( ct > 1){
//a[b-1] should also be print.
}

这个想法是这样的

  • As the numbers are sorted we will get a monotonic sequence.

  • We compare every number with one that came before. If there is duplicate they will appear next to next.

  • We only collect those numbers which appear multiple times.

此外,您还可以关注一些事情

  • 在方法内声明大变量有时会受到可用内存(自动存储持续时间)的限制。(可能有 stackoverflow 等)将其设为全局。(静态存储持续时间的东西)。

  • 变量名称有点可读

  • 如果使用排序算法,您可以获得帮助。

  • 了解不同算法的复杂性会有所帮助。问题是你的情况复杂度是 O(n^2)。比这更好的排序算法是流行的合并排序等。这个简单的想法解决了您的情况的问题。

您可以自己检查一下这段代码至少比您的版本更具可读性。这有助于避免小错误。

 int temp = a[0], count=0;
for(size_t i = 1; i<=len-1; i++)
{
if( arr[i] == arr[i-1])
count++;
else{
if( count > 1){
// a[i-1] should be printed.
}
count = 1;
}
}
if( count > 1){
//arr[len-1] should also be print.
}

关于c - 按升序排列多次绘制的数字。 [ C ],我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47348740/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com