1樓：立強
由於:若個數和累加合相同，則等差數列的平方和最小。
所以，空間複雜度是O(1)，時間複雜度是O(n)﹉好吧，再詳細點
遍歷過程需要產生5個值:最大值，最小值，個數，累加合，平方和。
例如6個數->最大值6，最小值1，累加和21，平方和等於1+4+9+16+25+36，則是等差數列，否則不是
2樓：
@Milo Yip 大神在給出答案的同時給我們提了個問題，讓我們改進下O(n)空間，看有沒有辦法給出O(1)空間，O(n)時間複雜度的演算法。
按原地置換排位的話其實是可以的。下面給出測試原始碼，大家可以驗證下。
#include
#include
#include
#include
int main( int argc, char** argv )
{ std::vectorvec;
for ( int i = 0; i < 1000;ivec.push_back( i * 2std::random_device rd;
std::mt19937 g( rdstd::shuffle( vec.begin(), vec.end(), g );//隨機化
// 原地置換排序
// 這裡可以檢驗下資料的合法性，比如vec.size()<2等非法情況
if (vec.size()<2printf( "NO"return 0auto p =std::minmax_element( vec.
begin(), vec.endint a1 = *p.first;
int an = *p.second;
int n = vec.size();
int d = ( an - a1 ) / (n-1);
if (d*(n-1) != (an-a1printf( "NO"return 0int from = 0;
int last = from;
int count = n * 2;
for ( ;from < n && count>=0;count-- )//最壞的情況下執行2n次int v = a1 + from*dint to = ( vec[from] - a1) / dif (vec[from] != vstd::swap(vec[from],vec[tocontinueelsefromprintf( "count=%d\n\n\n\n", count理論上如果count=0並且from
3樓：花椰菜君
給@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
，手機碼字就不詳細寫了。
4樓：Milo Yip
我嘗試不用排序。
掃瞄一次，計算最大值、最小值及總和，檢查 ，如不相等返回 false。時間。
通過 求等差項。
設乙個 bit array 表示 項是否存在。再掃瞄一次，如果全部項存在，返回 true，否則返回 false。時間，空間。
那麼，還有沒有方法令空間也呢？
如何構造新數列，證明 a n 是等差數列？
像這種題目的一般套路，就是將其配湊成形如 的形式，然後證明這個數列恆等於0，本題應該補充 否則這個數列就不是等差數列了。為了消去尾部的項，反覆往大了寫乙個式子做差 得到 再寫大乙個就是 得到上式稍加整理就可以得到 代入 可以求得 為了使這三項成等差數列必須要有 解得 此時，由此可以得出 這就說明了 ...
對於等差數列你能相信教材嗎？
莫名其妙想答。先把結論擺在前面 這部分的教材當然能被相信。我覺得教材這裡沒什麼不合理合情的。關於題主所說第一點 教材說的已經很嚴謹了。它強調了 每一 同乙個 清晰地表述了等差數列的概念且完全沒有造成歧義，這難道還不叫嚴謹？個人認為，加 都 字是完全沒有必要的。關於題主所說的第二點 理由1 題主的表示...
乙個有足夠多項公差不為0的等差數列任意打亂順序，是否總能抽出三項（不改變順序）依次成等差數列？
已登出 如果是無窮數列，那麼操作如下 若公差大於0 取a1取第乙個大於a1的項an 這個操作可以做到，因為1.公差大於0，對任意首項，2.給定原數列中任意位置的某數a1 小於a1的項的數量是有限的 所以an一定可以取到 第三項，即a1 2 an a1 在後面的項中必然存在，因為1.該項在原數列中存在...