Google : 求最长等差数列

给定一个未排序数组,找出其中最长的等差数列.

(PS O(n^2)的时间复杂度,这题如果能自己作出来相当不容易)

已经AC了, 把自己的代码贴上来, 这个地方需要自己写个哈希, 系统自带的__gnu_cxx::hash_map要快于unordered_map, 但是还是tle,
自己写的则快很多:

1. 
   
2. #include <iostream>
   
3. #include <algorithm>
   
4. #include <cstdio>
   
5. #include <cstdlib>
   
6. #include <cstring>
   
7. #include <map>
   
8. #include <unordered_map>
   
9. #include <unordered_set>
   
10. #include <ext/hash_map>
    
11. 
    
12. using namespace std;
    
13. using __gnu_cxx::hash_map;
    
14. 
    
15. int n;
    
16. int a[10001];
    
17. 
    
18. const int BUCKET_SIZE   = 42839;
    
19. const int NEXT_POS      = 7;
    
20. 
    
21. typedef struct _my_hash
    
22. {
    
23.     int _bucket[BUCKET_SIZE];
    
24.     int _key[BUCKET_SIZE];
    
25.     _my_hash()
    
26.     {
    
27.         memset(_bucket, 0, sizeof(_bucket[0]) * BUCKET_SIZE);
    
28.         memset(_key, 0, sizeof(_key[0]) * BUCKET_SIZE);
    
29.     }
    
30.     void insert(int key, int value)
    
31.     {
    
32.         int mod = key % BUCKET_SIZE;
    
33.         while (_key[mod] != 0)
    
34.         {
    
35.             mod = (mod + NEXT_POS) % BUCKET_SIZE;
    
36.         }
    
37.         _bucket[mod]    = value;
    
38.         _key[mod]       = key;
    
39.     }
    
40.     int find(int key)
    
41.     {
    
42.         int origin = key % BUCKET_SIZE;
    
43.         int mod = key % BUCKET_SIZE;
    
44.         while (_key[mod] != 0)
    
45.         {
    
46.             if (_key[mod] == key)
    
47.             {
    
48.                 return _bucket[mod];
    
49.             }
    
50.             mod = (mod + NEXT_POS) % BUCKET_SIZE;
    
51.             if (mod == origin)
    
52.             {
    
53.                 return -1;
    
54.             }
    
55.         }
    
56.         return -1;
    
57.     }
    
58. }my_hash_t;
    
59. 
    
60. //let's assume that sequence s(n) = a[i] s(n+1) = a[j]
    
61. //dp_matrix[i][j] represent the count of sequence in s
    
62. short int dp_matrix[10001][10001];
    
63. 
    
64. int main()
    
65. {
    
66.     //cin >> n;
    
67.     scanf("%d", &n);
    
68.     for (int i = 0; i < n; ++i)
    
69.         //cin >> a[i];
    
70.         scanf("%d", &a[i]);
    
71.     sort(&a[0], &a[n]);
    
72.     //unordered_map<int, int> element_map;
    
73.     //map<int, int> element_map;
    
74.     //hash_map<int, int> element_map(42839);
    
75.     my_hash_t my_hash;
    
76.     //hash_map<int, int> element_map;
    
77.     for (int i = 0; i < n; ++i)
    
78.     {
    
79.         //element_map[a[i]] = i;
    
80.         my_hash.insert(a[i], i);
    
81.     }
    
82.     memset(dp_matrix, 0, sizeof(dp_matrix[0][0]) * 10001 * 10001);
    
83.     short int max_len = 0;
    
84.     //const auto iter_end = element_map.end();
    
85. 
    
86.     for (int i = 0; i < n; ++i)
    
87.     {
    
88.         for (int j = i + 1; j < n; ++j)
    
89.         {
    
90.             int cur_delta = a[j] - a[i];
    
91.             int k_value = a[i] - cur_delta;
    
92.             //auto iter = element_map.find(k_value);
    
93.             //auto iter = element_map.end();
    
94.             int ret = my_hash.find(k_value);
    
95.             //if (iter != iter_end)
    
96.             if (ret != -1)
    
97.             {
    
98.                 //dp_matrix[i][j] = dp_matrix[iter->second][i] + 1;
    
99.                 dp_matrix[i][j] = dp_matrix[ret][i] + 1;
    
100.             }
     
101.             else
     
102.             {
     
103.                 dp_matrix[i][j] = 2;
     
104.             }
     
105.             if (dp_matrix[i][j] > max_len)
     
106.             {
     
107.                 max_len = dp_matrix[i][j];
     
108.             }
     
109.         }
     
110.     }
     
111.     cout << max_len << endl;
     
112.     return 0;
     
113. }
     

复制代码

1. 
   
2. #include <iostream>
   
3. #include <algorithm>
   
4. #include <cstring>
   
5. 
   
6. using namespace std;
   
7. 
   
8. int n;
   
9. int a[10001];
   
10. 
    
11. //let's assume that sequence s(n) = a[i] s(n+1) = a[j]
    
12. //dp_matrix[i][j] represent the count of sequence in s
    
13. short int dp_matrix[10001][10001];
    
14. 
    
15. int main()
    
16. {
    
17.     cin >> n;
    
18.     for (int i = 0; i < n; ++i)
    
19.         cin >> a[i];
    
20.     memset(dp_matrix, 0, sizeof(dp_matrix[0][0]) * 10001 * 10001);
    
21.     short int max_len = 0;
    
22. 
    
23.     for (int i = 0; i < n; ++i)
    
24.     {   
    
25.         for (int j = i + 1; j < n; ++j)
    
26.         {   
    
27.             bool delta_is_match = false;
    
28.             int cur_delta = a[j] - a[i];
    
29.             for (int k = i-1; k >= 0; --k)
    
30.             {   
    
31.                 int delta_i_to_k = a[i] - a[k];
    
32.                 if (delta_i_to_k == cur_delta)
    
33.                 {   
    
34.                     if (dp_matrix[i][j] < dp_matrix[k][i] + 1)
    
35.                         dp_matrix[i][j] = dp_matrix[k][i] + 1;
    
36.                     else
    
37.                         cout << "k:" << k << " i:" << i << " j:" << j << endl;
    
38.                     delta_is_match = true;
    
39.                     break;
    
40.                 }   
    
41.             }   
    
42.             if (delta_is_match == false)
    
43.             {   
    
44.                 dp_matrix[i][j] = 2;
    
45.             }   
    
46.             if (dp_matrix[i][j] > max_len)
    
47.             {   
    
48.                 max_len = dp_matrix[i][j];
    
49.             }   
    
50.         }   
    
51.     }   
    
52.     //for_each(&dp_matrix[0], &dp_matrix[n], [=](short int p[]){for_each(&p[0], &p[n],[](short int n){cout<<n<<' ';});cout<<endl;});
    
53.     cout << max_len << endl;
    
54.     return 0;
    
55. }
    

复制代码

我的代码我觉得应该是对的  但是wa, 我还在想为什么..我算出来的结果比正确结果低  有一个正确结果是25  我算出来是7....

1. 
   
2. 
   
3. #include <iostream>
   
4. #include <algorithm>
   
5. #include <cstdio>
   
6. #include <cstdlib>
   
7. #include <cstring>
   
8. #include <unordered_map>
   
9. #include <unordered_set>
   
10. 
    
11. using namespace std;
    
12. 
    
13. int n;
    
14. int a[10001];
    
15. 
    
16. //let's assume that sequence s(n) = a[i] s(n+1) = a[j]
    
17. //dp_matrix[i][j] represent the count of sequence in s
    
18. short int dp_matrix[10001][10001];
    
19. 
    
20. int main()
    
21. {
    
22.     //cin >> n;
    
23.     scanf("%d", &n);
    
24.     for (int i = 0; i < n; ++i)
    
25.         //cin >> a[i];
    
26.         scanf("%d", &a[i]);
    
27.     sort(&a[0], &a[n]);
    
28.     unordered_map<int, int> element_map;
    
29.     for (int i = 0; i < n; ++i)
    
30.     {   
    
31.         element_map[a[i]] = i;
    
32.     }   
    
33.     memset(dp_matrix, 0, sizeof(dp_matrix[0][0]) * 10001 * 10001);
    
34.     short int max_len = 0;
    
35.     const auto iter_end = element_map.end();
    
36. 
    
37.     for (int i = 0; i < n; ++i)
    
38.     {   
    
39.         for (int j = i + 1; j < n; ++j)
    
40.         {   
    
41.             int cur_delta = a[j] - a[i];
    
42.             int k_value = a[i] - cur_delta;
    
43.             auto iter = element_map.find(k_value);
    
44.             if (iter != iter_end)
    
45.             {   
    
46.                 dp_matrix[i][j] = dp_matrix[iter->second][i] + 1;
    
47.             }   
    
48.             else
    
49.             {   
    
50.                 dp_matrix[i][j] = 2;
    
51.             }   
    
52.             if (dp_matrix[i][j] > max_len)
    
53.             {   
    
54.                 max_len = dp_matrix[i][j];
    
55.             }   
    
56.         }   
    
57.     }   
    
58.     cout << max_len << endl;
    
59.     return 0;
    
60. }
    
61. 
    

复制代码

这个代码还是tle了  实在过不去了~~~~ 咋办?

平方的算法应该还是不难的吧？
首先做一个hash表，维护key={a,b} value=c，含义是以a开始的差为b的等差数列，最长为c
查找更新都是O(1)

然后两层循环，第一层for (int i=n-1;i>=0;--i)枚举数列头
第二层for (int j=i+1;j<n;++j)枚举数列第二项
在hash表里查找num[i],num[j]-num[i]并将其值更新

平方的算法应该还是不难的吧？
首先做一个hash表，维护key={a,b} value=c，含义是以a开始的差为b的等差数列，最长为c
查找更新都是O(1)

然后两层循环，第一层for (int i=n-1;i>=0;--i)枚举数列头
第二层for (int j=i+1;j
epic 发表于 2011-7-28 15:34

    哈哈,不错啊,这样做hash, 不过hash一般是万能解法......

回复 3# wwwyhx

1. #define MAXL 1000
   
2. int find(int a[], int n)
   
3. {
   
4.         int dp[MAXL][MAXL];
   
5.         int i, j;
   
6.         for(i = 1; i < n; i++) {
   
7.                 int p = 0;
   
8.                 for(j = 0; j < i; j++) {
   
9.                         dp[j][i] = 2;
   
10.                         while(p < j && a[p] + a[i] < 2 * a[j])
    
11.                                 p++;
    
12.                         if(p < j && a[p] + a[i] == 2 * a[j])
    
13.                                 dp[j][i] = max(dp[j][i], dp[p][j] + 1);
    
14.                 }
    
15.         }
    
16.         int ans = (n > 0);
    
17.         for(i = 1; i < n; i++)
    
18.                 for(j = 0; j < i; j++)
    
19.                         ans = max(ans, dp[j][i]);
    
20.         return ans;
    
21. 
    
22. }

复制代码

不用hash应该也能做，思路也是dp。dp[j][ i ]表示以a[j]和a[ i ]结尾的最长等差数列的长度。枚举最后两个元素，对于每一个a[j]和a[ i ]，都要找到a[p]，p < j，满足a[p] + a[ i ] == 2 * a[j]。然后dp[p][j] + 1去更新dp[j][ i ]。看起来是三层循环，但其实对于同一个i，p的位置是随着j增大而增大的，所以最里面的while循环对于每个i值最多是O(n)的代价。总的代价还是O(n^2)。

不过我这个好像要升序的数组才行。。{:4_84:}

回复  wwwyhx 不用hash应该也能做，思路也是dp。dp[j][ i ]表示以a[j]和a[ i ]结尾的最长等差数列的长度。枚举最后两个元素，对于每一个a[j]和a[ i ]，都要找到a，p < j，满足a + a[ i ] == 2 * a[j]。然后dp[j] + 1去更新dp[j][ i ]。看起来是三层循环，但其实对于同一个i，p的位置是随着j增大而增大的，所以最里面的while循环对于每个i值最多是O(n)的代价。总的代价还是O(n^2)。
darksteel 发表于 2011-7-29 13:06

    p++没道理,升序也不成

回复 6# wwwyhx
没有吧，升序的话应该是可以的，如果a[p]、a[j]、a[ i ]和a[q]、a[j+1]、a[ i ]分别构成等差数列，由于a[j+1]>a[j]，所以有a[q]>a[p]。所以对于同一个i，随着j的增加，能够与a[j]、a[ i ]构成等差数列的a[p]肯定是不断增大的。

回复  wwwyhx
没有吧，升序的话应该是可以的，如果a、a[j]、a[ i ]和a[q]、a[j+1]、a[ i ]分别构成等差数列，由于a[j+1]>a[j]，所以有a[q]>a。所以对于同一个i，随着j的增加，能够与a[j]、a[ i ]构成等差数列的a肯定是不断增大的。
darksteel 发表于 2011-7-30 12:47

    恩,是对的,你还真想的到.
    还有一种DP的就是:
    假设在升序数组里,由n...1对每个数x,两边扩展求a,b,使得x-a == b-x,这样f(b,x) = f(x,a)+1

楼主看看这个方法对不对；
用dp[i][dif] 表示以a[i]结尾，差为dif的等差数列长度最大值；
memset(dp,0,sizeof(dp));
for (i=2;i<=n;i++)
  for (j=1;j<=i-1;j++)
{
       int temp;
       if (a[i]-a[j]<0)  temp=base+(a[i]-a[j]);  //是负数给它加上个base （更好的办法时将差hash到一个数组中）
       else temp=a[i]-a[j];
       dp[i][temp]=max(dp[j][temp]+1,dp[i][temp]);
       ans=max(ans,dp[i][temp]);     
}

楼主看看这个方法对不对；
用dp[dif] 表示以a结尾，差为dif的等差数列长度最大值；
memset(dp,0,sizeof(dp));
for (i=2;i
swordsnow 发表于 2011-9-5 11:08

空间复杂度太高,我记得这种伪DP都是NP问题没办法了才用的