C 語言如何判斷等差數列？

問題： 判斷等差數列

描述： 輸入一個整數N，然後輸入N個整數。判斷這N個整數是否可以構建一個等差數列。（0&輸入： 第一行為一個整數N，第二行為N個整數。

輸出： 可以構成等差數列輸出True，否則輸出False。

示例：

(1)input： 10

5 3 2 1 7 6 4 8 10 9

output: True

(2)input： 5

4 6 3 2 7

output: False

提示：需要注意輸入的數可以沒有大小順序。@藍色@Milo Yip@RednaxelaFX@路人甲@RednaxelaFX@gh0stkey@gh0stkey

（大家還是重點在討論思路上吧。）

---

接著 @Milo Yip的思路：掃一遍可以確定首末項及公差，假如輸入的數列是一個等差數列，這時給出數列中任意一個元素的值就可以求出它在將數列排序後會位於第幾項。如果了解置換群的話，說到這裡應該就能想到O(1)額外空間的做法了～

代碼用純C寫的。請各位把重點放在演算法本身而非實現細節上。

#include &
#define LEN 1000
int a[LEN];
int main(){
int n, i;
scanf("%d", n);
for(i = 0; i &< n; i++) scanf("%d", a[i]); //find min max and compute delta int min = a[0], max = a[0]; for(i = 1; i &< n; i++){ if(min &> a[i])
min = a[i];
if(max &< a[i]) max = a[i]; } int delta = (max - min) / (n - 1); //try to sort the sequence int q; for(q = 0; q &< n; q++) while(a[q] != min + q * delta){ int pos, tmp; pos = (a[q] - min) / delta; if((a[q] - min) % delta != 0 || a[pos] == a[q]) break; tmp = a[pos]; a[pos] = a[q]; a[q] = tmp; } printf("%s ", q == n? "True": "False"); return 0; }

---

我嘗試不用排序。

掃描一次，計算最大值、最小值及總和，檢查 ，如不相等返回 false。時間。

通過 求等差項。

設一個 bit array 表示 項是否存在。再掃描一次，如果全部項存在，返回 true，否則返回 false。時間，空間。

那麼，還有沒有方法令空間也呢？

---

給@Milo Yip大大做個O(1)空間的補充。

在知道最小值a1，最大值an和差d之後，問題可以規約為滿足兩個條件

1.所有數都合法，即滿足等差數列表達式

2.不存在重複的元素

第1個條件通過減a1再模d為0判斷

第2個條件可以通過置換法來查重，O(1)空間即可。

最後就是O(1)空間，O(n)時間

由於知道等差數列表達式，任何合法數都可以對應為1到n的一個整數，才使得我們可以使用置換法查重，傳送門http://m.blog.csdn.net/article/details?id=26629475，手機碼字就不詳細寫了。

---

由於:若個數和累加合相同，則等差數列的平方和最小。

所以，空間複雜度是O(1)，時間複雜度是O(n)

﹉

好吧，再詳細點

遍歷過程需要產生5個值:最大值，最小值，個數，累加合，平方和。

例如6個數-&>最大值6，最小值1，累加和21，平方和等於1+4+9+16+25+36，則是等差數列，否則不是

---

第一種方法跟 @陳碩 的一樣，給出主要代碼

int n, x;
cin &>&> n;
vector& v;
for (int i = 0; i &< n; ++i) { cin &>&> x;
v.push_back(x);
}
if (n == 1) {
cout &<&< "yes" &<&< endl; return 0; } sort(v.begin(), v.end()); int d = v[1] - v[0]; auto it = adjacent_find(v.begin(), v.end(), [](int i, int j) {return (i + d) != j; }); if (it == v.end()) cout &<&< "yes" &<&< endl; else cout &<&< "no" &<&< endl;

sort 的時間複雜度是 O(nlogn)，adjacen_find 的時間複雜度是 O(n)，總的時間複雜度是O(nlogn)。

第二種方法類似於 @Milo Yip 的思路，不用 sort

（已經修改過了）

int n, x, t = 0;
int res1 = 1, res2 = 1;
cin &>&> n;
vector& v;
for (int i = 0; i &< n; ++i) { cin &>&> x;
v.push_back(x);
}
if (n == 1) {
cout &<&< "yes" &<&< endl; return 0; } auto m = minmax_element(v.begin(), v.end()); int d = (*m.second - *m.first) / (v.size() - 1); for (int i = 0; i &< n; ++i) { int index = (v[i] - *m.first) / d + 1; t += index; res1 = index; res2 = i + 1; } if (t == ((1 + n) * n) &>&> 1 res1 == res2)
cout &<&< "yes" &<&< endl; else cout &<&< "no" &<&< endl;

minmax_elemnt 的時間複雜度是 O(n)，遍歷的時間複雜度也是 O(n)，總的時間複雜度是 O(n)，如果說空間複雜度指額外的開銷，那麼這個空間複雜度就是 O(1)。

寫錯沒有..求鑒定

---

給 @神妙可 的答案補個代碼, 思路跟 @Milo Yip 的答案差不多, 時間複雜度O(n), 空間複雜度O(1)

#include &
#include &
#include &
#include &

bool hasDup(std::vector& vec, int min, int max, int d) {
for (int i = 0; i &< vec.size(); ++i) { while (vec[i] != (min + d * i)) { int idx = (vec[i] - min) / d; if (vec[i] == vec[idx]) return true; std::swap(vec[i], vec[idx]); } } return false; } bool isDengcha(std::vector& vec) {
if (vec.size() == 1)
return true;
auto minmax = std::minmax_element(vec.begin(), vec.end());
int min = *(minmax.first);
int max = *(minmax.second);
if (min == max)
return true;
if ((max - min) % (vec.size() - 1) != 0) // 整數等差數列必然可以整除
return false;
int d = (max - min) / (vec.size() - 1);
if (hasDup(vec, min, max, d))
return false;
for (int x : vec) {
if ((x - min) % d != 0)
return false;
}
return true;
}

int main() {
std::vector& v1{3, 2, 1, 0, -1};
std::vector& v2{1, 3, 5, 7, 9, 11};
std::vector& v3{2, 2, 2, 2, 2, 2};
std::vector& v4{3};
std::vector& v5{3, 4};
assert(isDengcha(v1));
assert(isDengcha(v2));
assert(isDengcha(v3));
assert(isDengcha(v4));
assert(isDengcha(v5));

v3[2] = 3;
assert(!isDengcha(v3));
v1[2] = 0;
assert(!isDengcha(v1));
v5[1] = 10;
assert(isDengcha(v5));
}


---

@Milo Yip 大神在給出答案的同時給我們提了個問題，讓我們改進下O(n)空間，看有沒有辦法給出O(1)空間，O(n)時間複雜度的演算法。

按原地置換排位的話其實是可以的。下面給出測試源碼，大家可以驗證下。

#include &
#include &
#include &
#include &
int main( int argc, char** argv )
{
std::vector&vec;
for ( int i = 0; i &< 1000;i++ ) { vec.push_back( i * 2 ); } std::random_device rd; std::mt19937 g( rd() ); std::shuffle( vec.begin(), vec.end(), g );//隨機化 // 原地置換排序 // 這裡可以檢驗下數據的合法性，比如vec.size()&<2等非法情況 if (vec.size()&<2) { printf( "NO" ); return 0; } auto p =std::minmax_element( vec.begin(), vec.end() ); int a1 = *p.first; int an = *p.second; int n = vec.size(); int d = ( an - a1 ) / (n-1); if (d*(n-1) != (an-a1)) { printf( "NO" ); return 0; } int from = 0; int last = from; int count = n * 2; for ( ;from &< n count&>=0;count-- )//最壞的情況下執行2n次
{
int v = a1 + from*d;
int to = ( vec[from] - a1) / d;
if (vec[from] != v)
{
std::swap(vec[from],vec[to]);
continue;
}
else
{
from++;
}
}
printf( "count=%d

", count );
//理論上如果count=0並且from&

---

sort + adjacent_find

---

C語言代碼

1、先讀到數組中。

2、再用歸併排序（n log n）

void merge_sort_recursive(int arr[], int reg[], int start, int end) {
if (start &>= end)
return;
int len = end - start, mid = (len &>&> 1) + start;
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
merge_sort_recursive(arr, reg, start1, end1);
merge_sort_recursive(arr, reg, start2, end2);
int k = start;
while (start1 &<= end1 start2 &<= end2) reg[k++] = arr[start1] &< arr[start2] ? arr[start1++] : arr[start2++]; while (start1 &<= end1) reg[k++] = arr[start1++]; while (start2 &<= end2) reg[k++] = arr[start2++]; for (k = start; k &<= end; k++) arr[k] = reg[k]; } void merge_sort(int arr[], const int len) { int reg[len]; merge_sort_recursive(arr, reg, 0, len - 1); }

3、再寫一個函數，用一個 diff_value = arr[1] - arr[0]

再用for循環判斷一下。

n log n + n

---

給 @陳碩補段代碼

#include &
#include &
#include &
int main() {
int n;
std::vector& vec;
std::cin &>&> n;
if (n == 1) {
int x;
std::cin &>&> x;
vec.push_back(x); // what i think is unnecessary
std::cout &<&< "True" &<&< std::endl; } else { for (;n--;) { int x; std::cin &>&> x;
vec.push_back(x);
}
std::sort(std::begin(vec), std::end(vec));
const int d = vec[1] - vec[0];
const auto res = std::adjacent_find(std::begin(vec), std::end(vec), [d](int a, int b) {
return b - a != d;
});
if (res == std::end(vec)) {
std::cout &<&< "True"; } else { std::cout &<&< "False"; } } } /* 10 5 3 2 1 7 6 4 8 10 9 5 4 6 3 2 7 */

最直接的方法，複雜度，對1000的數據夠用了

---

nlogn的演算法，最簡單，排序，比較

---

golang也來湊個熱鬧

---

先排個序，然後從i=2開始，判斷ai-a(i-1)是不是等於a1-a0.

---

推薦閱讀：