c++ - 算术序列 - 检查

Question

检查是否可以根据指定的数字序列创建算术序列的最有效方法是什么？

目前我对序列进行排序，然后执行此操作:

#include<bits/stdc++.h>
using namespace std;

static bool sort_using_greater_than(float u, float v)
{
return u > v;
}


int main()
{
int licznik=0, i=0;
double number[100000];
while(~scanf("%f", &number[i]))
{
     i++;
     licznik++;
}
 sort(number,number+100, sort_using_greater_than);

for(int i = 1; i < licznik-1; i++)
{
    if(number[i] - number[i+1] != number[0] - number[1])
    {
        puts("NO");
        return 0;
    }
}
puts("YES");

用于测试:

1. 1.0 5.0

我的代码返回 YES，为什么？

enter code here
double search_min(double tab[], int n)
{
double min = tab[0];
for(int i = 1; i < n; i++)
{
    if(min > tab[i])
        min = tab[i];
return min;
}

而且，我如何找到两个最小的元素？

Answer 1

问题不清楚，但如果它的意思是“检查给定的数字是否可以从一个算术序列中重新排列”，那么就不需要排序。

• 找到最小的元素，在O(N)中，令a;

• 找第二小的，在O(N)中，令b;

• 在 O(N) 中清除一个 N 位的数组；

• 对于每个数字 c，计算 (c - a)/(b - a)；如果这不是 [0,n-1] 范围内的整数，则答案是否定的。否则，设置该索引处的位(每个元素在 O(1) 中完成)；

• 检查所有位是否已在 O(N) 中设置。

整个过程耗时O(N)。