算術序列檢查

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.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-a）/（b-a）;對於每個數c，計算（c-a）/（b-a）;如果這不是範圍[0，n-1]中的整數，則答案是否定的。否則，在該索引處設置該位（在每個元素的O（1）中完成）;

• 檢查是否所有位都已設置爲O（N）。

整個過程需要時間O（N）。

Answer 2

O（n）是最好的你會得到簡單的性質，你必須檢查每一個元素。

我已經在C++ 14標準代碼中實現了Yves Daoust的算法（有一些小的優化）以及您自己的算法。

這裏是你的：

int main(int argc, char* argv[]) { 

    if(argc == 1) return 0; 

    //Copy command args to vector of strings. 
    std::size_t number_count = argc - 1; 
    std::vector<std::string> cmd_args(number_count); 
    std::copy(argv + 1, argv + argc, cmd_args.begin()); 

    //Copy convert vector of strings to vector of ints. 
    std::vector<int> values(number_count); 
    auto v_begin = values.begin(); 
    for(auto s : cmd_args) { 
     (*v_begin) = std::stoi(s); 
     ++v_begin; 
    } 

    //Sort values in ascending order. 
    std::sort(values.begin(), values.end()); 

    //Get smallest two values. 
    std::pair<int, int> two_smallest_values(*values.cbegin(), *(values.cbegin() + 1)); 

    //Calculate differences between each successive number 
    std::vector<int> differences(values.size() - 1); 
    for(std::size_t i = 0; i < values.size() - 1; ++i) { 
     differences[i] = std::abs(values[i] - values[i + 1]); 
    } 

    //All values in differences must be the same. 
    if(std::all_of(differences.cbegin(), differences.cend(), [=](int i) { return i == *differences.cbegin(); })) { 
     std::cout << "YES\n"; 
    } else { 
     std::cout << "NO\n"; 
    } 

    return 0; 
} 

這裏是伊夫·達斯特的算法：

int main(int argc, char* argv[]) { 
    if(argc == 1) return 0; 

    //Copy command args to vector of strings. 
    std::size_t number_count = argc - 1; 
    std::vector<std::string> cmd_args(number_count); 
    std::copy(argv + 1, argv + argc, cmd_args.begin()); 

    //Copy convert vector of strings to vector of ints. 
    auto v_begin = values.begin(); 
    for(auto s : cmd_args) { 
     (*v_begin) = std::stoi(s); 
     ++v_begin; 
    } 

    //Sort values in ascending order. 
    std::sort(values.begin(), values.end()); 

    //Get smallest two values. 
    std::pair<int, int> two_smallest_values(*values.cbegin(), *(values.cbegin() + 1)); 

    std::vector<bool> bits(values.size()); 

    bool result = true; 

    int smallest_diff = (two_smallest_values.second - two_smallest_values.first); 
    for(auto v : values) { 
     int numerator = v - two_smallest_values.first; 
     int denominator = smallest_diff; 
     if(numerator % denominator != 0) { 
      result = false; 
      break; 
     } 
     std::size_t i = numerator/denominator; 
     if(i < 0 || i >= values.size()) { 
      result = false; 
      break; 
     } 
     bits[i] = true; 
    } 

    if(result == false) { 
     std::cout << "NO\n"; 
     return 0; 
    }   

    //Convert vector of bools (bit-packed) to an unsigned int. 
    unsigned long long bits_value = 0; 
    unsigned long long i = 0; 
    for(auto b : bits) { 
     bits_value |= (b << i++); 
    } 

    //Optimization: Single calculation to determine if all bits are set: 
    if(std::abs(bits_value - (std::pow(2.0, bits.size()) - 1) < 0.01)) { 
     std::cout << "YES\n"; 
    } else { 
     std::cout << "NO\n"; 
    } 

    return 0; 
}