【C# 每日一题2】求最长等差数列
题目需求：
在一个升序排列好的数列里面找到最长的等差数列
例子：1 3 5 6 8 9 10 12 13 14
子数列有(两项的不在列举）
1 3 5
1 5 9 13
3 6 9 12
3 8 13
5 9 13
.....
得出的最长的等差数列应该是：6 8 10 12 14
大家各抒己见，踊跃发言，写一下自己的想法吧！
每日一题1 得到了版主的推荐，我们有了一个不错的开始，希望大家都加入进来，一起讨论，共同进步！！
[解决办法]
计算机吗，当然是穷举了，
for (int i = 0; i < length; i++)
{
for (int j = 0; j < length; j++)
{
//根据i，j下标取出两个数，假设就是等差数列的前两位，那么接着再求后面的。
//如果优化，可以记下等差的差值，如果发现这个差值已经处理过，那直接就可以跳过
}
}
[解决办法]
#include "stdio.h"#include <map>using namespace std;#define MAX_LEN 1000int data[MAX_LEN];int length;int best;int bestdelta;int beststart;void Run(){ map<int,int> alldata; map<int,int> useddelta; scanf("%d",&length); for(int i = 0;i < length;i++) { scanf("%d",data+i); alldata[data[i]] = 0; } if(length == 1) { printf("%d\n",data[0]); return; } best = 2; bestdelta = data[1]-data[0]; beststart = data[0]; for(int i = 0;i < length-best+1;i++) { useddelta.clear(); for(int j = 0;j <= i;j++)useddelta[data[i]-data[j]] = 0; for(int j = i+1;j < length-best+2;j++) { if(useddelta.find(data[j]-data[i]) != useddelta.end())continue; int delta = data[j]-data[i]; int curlen = 2; int curdata = data[j]; while(true) { if(alldata.find(curdata+delta) != alldata.end()) { curlen++; curdata += delta; } else break; } if(curlen > best) { best = curlen; bestdelta = delta; beststart = data[i]; } } } for(int i = 0;i < best-1;i++,beststart += bestdelta)printf("%d ",beststart); printf("%d\n",beststart);}int main(){ Run(); return 0;}
[解决办法]
static void Main(string[] args) { List<NumListHeader> allList = new List<NumListHeader>(); string[] s = Console.ReadLine().Split(' '); NumListBody max = null; int[] allNum = s.ToList().ConvertAll<int>((x) => { return int.Parse(x); }).ToArray(); allNum.ToList().ForEach((n)=>{ allList.ForEach((l) => { bool newlist = l.bodys.Count==0; l.bodys.ForEach((b) => { if (n == b.Step * b.length + l.Start) { b.length++; if (max == null || b.length > max.length) { max = b; } } else if (n > b.Step * b.length + l.Start) { l.bodys.Remove(b); } else { newlist = true; } }); if (newlist) { l.bodys.Add(new NumListBody() { length =2, Step = n-l.Start, Start = l.Start }); } }); allList.Add(new NumListHeader() { Start = n }); }); Console.WriteLine("start:{0},step:{1},length:{2}", max.Start, max.Step, max.length); Console.Read(); } } class NumListBody { public int Start; public int Step; public int length; } class NumListHeader { public NumListHeader() { bodys = new List<NumListBody>(); } public int Start; public List<NumListBody> bodys; }
[解决办法]
算法基本上在注释中解释清楚了。总的思想是用liveSeq追踪所有可能的等差序列，把所有可能的在n结束的序列记录在liveSeq的第n个位置。
#include <iostream>#include <cstring>#include <utility>#include <vector>using namespace std;int n;int a[10001];int flag[10001];/** * liveSeq[i] 是一个由（d,l）组成的对子，该数组表示在给定的序列中有差为d,长为l,结束在i的等差序列。 * 处理完值为n的项后，该数组中总的对子的个数为O(nlgn)。 */vector< pair<int, int> > liveSeq[10001];int main() { memset(flag, 0, sizeof(flag)); cin >> n; //n = 10000; for (int i=0; i<n; i++) { cin >> a[i]; //a[i] = i; flag[a[i]] = 1; } int maxai = a[n-1]; int maxlength = 2; int maxEnd = a[1]; int maxDiff = a[1]-a[0]; for (int i=0; i<n; i++) { int next = a[i]; // a[i]可以和a[j]（j<i）构成新的等差序列 // 下面循环中注1处的检测条件是根据这样一个事实： // 如果a[i]-a[j]太大的话，即使这个序列能一直延伸到最大值，也不可能有足够多的项来超过 // 已有的maxlength。 for (int j=i-1; j>=0; j--) { if (maxlength> 2 and next-a[j] > (maxai-next)/(maxlength-2)) { //注1 break; } if (flag[2*a[j]-a[i]] == 0 and (2*a[i]-a[j]<=maxai) and (flag[2*a[i]-a[j]] == 1)) { liveSeq[2*a[i]-a[j]].push_back(make_pair(a[i]-a[j], 3)); } } // 扩展原来在next结束的数列 for (int j = 0; j<liveSeq[next].size(); j++) { pair<int, int> seq = liveSeq[next][j]; if (next+seq.first <= maxai and flag[next+seq.first] == 1) { // 可以扩展 seq.second += 1; liveSeq[next+seq.first].push_back(seq); } else { // 不能再扩展了，看它的长度是否破了记录 if (seq.second > maxlength) { maxlength = seq.second; maxEnd = next; maxDiff = seq.first; } } } // 原来结束在next的序列或者在下一站获得了新生，或者已经被盖棺定论了，可以清除它们的记录了 liveSeq[next].clear(); } // print the sequence int start = maxEnd - (maxlength-1)*maxDiff; while (start <= maxEnd) { cout << start << " "; start += maxDiff; } cout << endl;}
[解决办法]
前段时间刚好想过这个问题，有2个方法，一个是n^2空间,n^2时间的，一个是m*n/k时间（m为最大数与最小数的差，k为最长序列的长度），O(n)空间的，以上两个方法要求数据中没有重复的元素，并且需要先对数据排序
不过个人感觉应该有更好的方法
public static void Solve2(int[] items) { int[,] matrix = new int[items.Length, items.Length]; int maxLength = 0, maxInc = -1, last = -1; for (int i = 1; i < items.Length - 1; i++) { int j = i - 1, k = i + 1; while (j >= 0 && k < items.Length) { if (items[j] + items[k] > items[i] * 2) j--; else if (items[j] + items[k] < items[i] * 2) k++; else { matrix[i, k] = matrix[j, i] == 0 ? 3 : matrix[j, i] + 1; if (matrix[i, k] > maxLength) { maxLength = matrix[i, k]; last = items[k]; maxInc = items[i] - items[j]; } j--; k++; } } } Console.WriteLine("{0} {1} {2}", maxLength, maxInc, last); } public static void Solve1(int[] items) { Dictionary<int, int> hash = new Dictionary<int, int>(); int max = items.Max() - items.Min(); int maxLength = 2, maxInc = -1, last = -1; for (int inc = 1; inc < max; inc++) { if (inc * maxLength > max) break; hash.Clear(); hash.Add(items[0], 1); for (int i = 1; i < items.Length; i++) { if (hash.ContainsKey(items[i] - inc)) { int value = hash[items[i] - inc]; hash.Remove(items[i] - inc); hash.Add(items[i], value + 1); if (value + 1 > maxLength) { maxLength = value + 1; maxInc = inc; last = items[i]; } } else if (!hash.ContainsKey(items[i])) hash.Add(items[i], 1); } } Console.WriteLine("{0} {1} {2}", maxLength, maxInc, last); }
[解决办法]
NumListBody储存一个数列的起始 步长 长度，NumListHeader储存所有以同一数字开始的数列，遍历每一个数n，检查n和全部比它小的数m，尝试将n归入所有以m开头的数列中，如不能归入所有m开头数列，则增加一个m,n为起始2元素的数列，如此至最后一个数字，找出其中最长的，优化的方法主要是检查一个数列如果无法增长或者即使增长也无法达到目前最长数列时，就放弃此数列。
[解决办法]
static void Main(string[] args) { int[] array = new int[] { 1, 3, 5, 6, 8, 9, 10, 12, 13, 14, 20, 22, 23, 24, 25, 26, 28, 30, 34, 38, 42, 46, 50 }; ISet<Int32> set = new HashSet<Int32>(array); for (int length = array.Length; length > 2; length--) { for (int startPos = 0; startPos + length <= array.Length; startPos++) { int first = array[startPos]; int diff = array[array.Length - 1] - first; int maxStep = diff / (length - 1); for (int step = 1; step <= maxStep; step++) { bool valid = true; for (int i = 1; i < length; i++) { int x = first + i * step; if (!set.Contains(x)) { valid = false; break; } } if (valid) { Console.WriteLine("length: {0}, first: {1}, step: {2}", length, first, step); goto end; } } } } end: Console.ReadKey(); }
[解决办法]
#include <iostream>#include <algorithm>using namespace std;const int MaxN = 10000000;int f[MaxN + 2];int pre[MaxN + 2];int a[MaxN];int best;int bestAns_i;int bestAns_d;int N;int count(int d) { int i; f[0] = 1; for (i = 1; i < N; ++i) { f[i] = 1; pre[i] = -1; int * p = lower_bound(a + 0, a + i, a[i] -d); if (p != a + i && *p == a[i] - d) { int pos = p -a; f[i] = f[pos] + 1; pre[i] = pos; } if (f[i] > best) { best = f[i]; bestAns_i = i; bestAns_d = d; } } return 0;}void showAns() { int n = a[bestAns_i]; while(binary_search(a+0,a+bestAns_i + 1, n) ) { printf("%d ", n); n -= bestAns_d; } printf("\n");}void run() { int i = 0; int tmp; int max = -99999999, min = 99999999; while(1) { if (scanf("%d", &tmp) != 1) break; a[i] = tmp; ++i; max = std::max(max, tmp); min = std::min(min, tmp); } N = i; int maxD = max - min; best = -99999999; for (int d = 0; d <= maxD; ++d) { count(d); } printf("%d\n", best); showAns();}int main() { run(); return 0;}
[解决办法]
更正一下输出格式：
#include <iostream>#include <algorithm>using namespace std;const int MaxN = 10000000;int f[MaxN + 2];int pre[MaxN + 2];int a[MaxN];int best;int bestAns_i;int bestAns_d;int N;int count(int d) { int i; f[0] = 1; for (i = 1; i < N; ++i) { f[i] = 1; pre[i] = -1; int * p = lower_bound(a + 0, a + i, a[i] -d); if (p != a + i && *p == a[i] - d) { int pos = p -a; f[i] = f[pos] + 1; pre[i] = pos; } if (f[i] > best) { best = f[i]; bestAns_i = i; bestAns_d = d; } } return 0;}void showAns() { int n = a[bestAns_i]; while(binary_search(a+0,a+bestAns_i + 1, n) ) { //~ printf("%d ", n); n -= bestAns_d; } n += bestAns_d; while(n <= a[bestAns_i]) { printf("%d ", n); n += bestAns_d; } printf("\n");}void run() { int tmp; int max = -99999999, min = 99999999; scanf("%d", &N); int i; for (i = 0; i < N; ++i) { scanf("%d", &a[i]) ; tmp = a[i]; max = std::max(max, tmp); min = std::min(min, tmp); } int maxD = max - min; best = -99999999; for (int d = 0; d <= maxD; ++d) { count(d); } //~ printf("%d\n", best); showAns();}int main() { run(); return 0;}
[解决办法]
//最终的计算结果 static List<int> list = new List<int>(); //计算方法 static void newCalc(int[] nums) { Array.Sort(nums); int length = nums.Length; //差值 int sp = 0; //计算出的等差队列 第一个元素为 nums[i] for (int i = 0; i < length - 1; i++) { //计算出的等差队列 第二个元素为 nums[j] for (int j = i + 1; j < length; j++) { //差 sp = nums[j] - nums[i]; //此次计算出的等差队列 List<int> slist = new List<int>(); slist.Add(nums[i]); slist.Add(nums[j]); int end = nums[j]; for (int n = j + 1; n < length; n++) { //继续向后找 if (nums[n] - end < sp) { continue; } // if (nums[n] - end > sp) { break; } //添加到队列，向后找 if (nums[n] - end == sp) { slist.Add(nums[n]); end = nums[n]; } } //判断 if (slist.Count > list.Count) { list = slist; } } } } static void Main() { string str = "1 5 6 9 10 13 14 18 22"; string[] args = str.Split(' '); int[] nums = new int[args.Length]; for (int i = 0; i < args.Length; i++) { nums[i] = int.Parse(args[i].Trim()); } newCalc(nums); //打印 list集合 string result = ""; for (int i = 0; i < list.Count; i++) { result += list[i].ToString() + ","; } Console.WriteLine(result); }
[解决办法]
/*
* 1.先计算出所有的公差d，存放在数组中
* 2.从数列的第1项开始，根据数组中的公差生成n个等差数列，存放在ArrayList里
* 3.ArrayList里长度最大的一项就是所求结果
*
* 由于在LINUX下，不方便配置C#环境，就用java写了。
*/
import java.util.ArrayList;
import java.util.HashMap;
public class Test {
public static void main(String[] args){
System.out.println(new Seq(new int[]{1,3,5,6,8,9,10,12,13,14}).getArray().toString());
System.out.println(new Seq(new int[]{1,2,4,6,8,9,12,13,14,16,19,20,22,23,24}).getArray().toString());
}
}
class Seq{
int[] num;
Integer[] d;//公差
ArrayList <ArrayList <Integer> > seq;
public Seq(int[] array){
num = array;
}
public ArrayList <Integer> getArray(){
d = getD();
seq = new ArrayList <ArrayList <Integer> > (d.length * d.length);
for(int k = 0;k < d.length;k++){
for(int i = 0;i < num.length;i++){
int n = d[k];
ArrayList <Integer> array = new ArrayList <Integer> ();
array.add(num[i]);
for(int j = i;j < num.length;j++){
if(num[i] + n == num[j]){
array.add(num[j]);
n += d[k];
}
}
seq.add(array);
}
}
int max = seq.get(0).size();
int index = 0;
for(int i = 1; i < seq.size();i++){
if(seq.get(i).size() > max){
max = seq.get(i).size();
index = i;
}
}
return seq.get(index);
}
private Integer[] getD(){
HashMap <Integer, Integer> hm = new HashMap <Integer, Integer> ();
for(int i = 0;i < num.length;i++){
for(int j = i + 1;j < num.length;j++){
int key = j - i;
if(!hm.containsKey(key)){
hm.put(key, 1);
}
}
}
Integer[] array = new Integer[hm.size()];
hm.keySet().toArray(array);
return array;
}
}
结果：
[6, 8, 10, 12, 14]
[4, 8, 12, 16, 20, 24]
[解决办法]
[code=C/C++][/code]
//用分治法来解决此问题， 只处理了递增等差数列
//在右字串中得到最长等差数列后尝试向左扩展
void extendToLeft(int *arr, int lowerbound,
/*in out */int *prightsubindex,
/*in out */int *prightsublen)
{
int rightequdiff = 0, index = *prightsubindex - 1;
if (*prightsublen == 1)
{
if (arr[*prightsubindex - 1] < arr[*prightsubindex])
{
(*prightsubindex) = (*prightsubindex) - 1;
*prightsublen = 2;
}
}
else
{
rightequdiff = arr[*prightsubindex + 1] - arr[*prightsubindex];
for (; index >= lowerbound && arr[index + 1] - arr[index] == rightequdiff; index--);
*prightsublen += *prightsubindex - (index + 1);
*prightsubindex = index + 1;
}
}
//在左字串中得到最长等差数列后尝试向右扩展
void extendToRight(int *arr, int upperbound,
int leftsubindex, /*in out */int *pleftsublen)
{
int leftequdiff = 0, index = leftsubindex + *pleftsublen;
if (*pleftsublen == 1)
{
if (arr[leftsubindex] < arr[leftsubindex + 1])
*pleftsublen = 2;
}
else
{
leftequdiff = arr[leftsubindex + 1] - arr[leftsubindex];
for (; index <= upperbound && arr[index] - arr[index-1] == leftequdiff; index++);
*pleftsublen = index - leftsubindex;
}
}
// 返回值为最长等差数列的长度， int* pll为输出参数， 为数列的起始索引（以0为基础）
int subequaldifference(int *arr, int left, int right, int* pll)
{
if (left > right)
return -1;
if (left == right)
{
*pll = left;
return 1;
}
if (left + 1 == right)
{
if (arr[left] <= arr[right])
{
*pll = left;
return 2;
}
else
return -1;
}
int mid = (left + right) / 2, leftsublenidx = 0, rightsublenidx = 0, len = 0;
int sublenl = subequaldifference(arr, left, mid, &leftsublenidx);
int sublenr = subequaldifference(arr, mid + 1, right, &rightsublenidx);
if (sublenl > 0)
extendToRight(arr, right, leftsublenidx, &sublenl);
if (sublenr > 0)
extendToLeft(arr, sublenl > 0 ?leftsublenidx:left, &rightsublenidx, &sublenr);
if (sublenl >= sublenr)
{
*pll = leftsublenidx;
len = sublenl;
}
else
{
*pll = rightsublenidx;
len = sublenr;
}
return len;
}
void equal_difference()
{
int dataarray[] = {-1, 1, 3, 5, 7, 9, 9, 11, 13, 15,
17, 10, 19, 21, 23, 25, 27, 29, 31, 33,
35, 37};
int iNum = sizeof(dataarray)/sizeof(dataarray[0]);
int longest = 0, len = 0;
len = subequaldifference(dataarray, 0, iNum - 1, &longest);
}
[解决办法]
/******************************************************************** purpose: 微软笔试题 求随机数构成的数组中找到长度大于=3的最长的等差数列 输出等差数列由小到大: 如果没有符合条件的就输出 格式： 输入[1,3,0,5,-1,6] 输出[-1,1,3,5] 要求时间复杂度，空间复杂度尽量小 *********************************************************************/#include <iostream>#include <set>#include <vector>using namespace std;// 归并排序void Merge(int rOrg[], int rBuf[], int from, int mid, int to){ int i = from; int j = mid + 1; int k = from; while (i <= mid && j <= to) { if (rOrg[i] <= rOrg[j]) rBuf[k++] = rOrg[i++]; else rBuf[k++] = rOrg[j++]; } if (i <= mid) while (i <= mid) rBuf[k++] = rOrg[i++]; else while (j <= to) rBuf[k++] = rOrg[j++]; while(k>from) rOrg[--k] = rBuf[k];}// 归并排序void MergeSort(int r[], int rBuf[], int from, int to){ if (from == to) rBuf[from] = r[from]; else { int mid = (from + to) / 2; MergeSort(r, rBuf, from, mid); MergeSort(r, rBuf, mid + 1, to); Merge(rBuf, r, from, mid, to); }}// 二分查找int BinarySearch(int *r, const int &item, int left, int right){ int middle; while(left <= right) { middle = (left + right)/2; if(r[middle] == item) return middle; else if(r[middle] < item) left = middle + 1; else right = middle - 1; } return -1;}// 求随机数构成的数组中找到长度大于=3的最长的等差数列void MaxLenEQDistSubArray(int rOrg[], int len) { if (rOrg == NULL || len < 3) { return; } int *rBuf = new int[len]; // 用于归并排序 MergeSort(rOrg, rBuf, 0, len-1); int** steps = new int*[len]; int* stepP; int i, j, k, jEnd, left, right=len-1, curEndI, curDist, curLastItem, curLen=0, maxEndI, maxDist, maxLastItem, maxLen=2; // 初始化 步数数组 for (i = 0; i < len; i++) { steps[i] = new int[len-i]; stepP = steps[i]; for (int j = len-i-1; j >= 0; j-- ) { stepP[j] = 0; } } // 开始查找最大等差子数组 for (i = 0; i < len; i++) { jEnd = len - i; stepP = steps[i]; for (j = i + 1; j < jEnd; j++) { if (stepP[j-i]) { continue; } stepP[j-i]=1; curLastItem = rOrg[j]; curDist = rOrg[j]-rOrg[i]; left = j; curLen = 2; while ((k=BinarySearch(rOrg, curLastItem+curDist, left+1, right)) != -1) { //是否存在下一等差数 curLen++; curLastItem += curDist; steps[left][k-left] = 1; left = k; } if (curLen > maxLen) { maxLen = curLen; maxLastItem = curLastItem; maxDist = curDist; } } } // 输出结果 if (maxLen >= 3) { int start = maxLastItem - maxDist*(maxLen-1); cout<<"max length:"<<maxLen<<endl; cout<<"max sub array: "; while(maxLen--) { cout<<start<<" "; start += maxDist; } } else { cout<<"no GT 3 length sub array"<<endl; } delete[] rBuf; delete[] steps;}void Test_MaxLenEQDistSubArray(){ //// test MergeSort //const int LEN = 8; //int rOrg[LEN]={10,3,5,1,9,34,54,565},rBuf[LEN]; //MergeSort(rOrg, rBuf, 0, LEN-1); //for (int i = 0; i < LEN; i++) // cout << " " << rOrg[i]; int rOrg[] = {1,3,0,5,-1,6}; MaxLenEQDistSubArray(rOrg, sizeof(rOrg)/sizeof(rOrg[0]));}
[解决办法]
我想我的可能差不多最快了，首先最坏的情况理论上讲每两个数都要减一次，如果比这个还要多，那算法肯定不是最好的，我的做到了这一点。
思路主要见核心那部分代码
// 开始查找最大等差子数组 for (i = 0; i < len; i++) { jEnd = len - i; stepP = steps[i]; for (j = i + 1; j < jEnd; j++) { if (stepP[j-i]) { continue; } stepP[j-i]=1; curLastItem = rOrg[j]; curDist = rOrg[j]-rOrg[i]; left = j; curLen = 2; while ((k=BinarySearch(rOrg, curLastItem+curDist, left+1, right)) != -1) { //是否存在下一等差数 curLen++; curLastItem += curDist; steps[left][k-left] = 1; left = k; } if (curLen > maxLen) { maxLen = curLen; maxLastItem = curLastItem; maxDist = curDist; } } }
[解决办法]
http://blog.csdn.net/wcyoot/archive/2011/05/22/6437382.aspx