I wrote the code in C# (replaced leading spaces to dots to keep indentation). -benbenli(大岭) @佛州华人论坛:佛州枫下论坛 The Rolia Forum of Florida

工作学习 / 学科技术 / 一道面试题，大家给出出主意哈，我一点头绪都没有 -unhappy_popular(unhappy_popular); 2016-2-8 {1453} (#9934209@0)
本文发表在 rolia.net 枫下论坛An arithmetic series consists of a sequence of terms such that each term minus its immediate predecessor gives the same result. For example, the sequence 3,7,11,15 is the terms of the arithmetic series 3+7+11+15; each term minus its predecessor equals 4. (Of course there is no requirement on the first term since it has no predecessor.)

Given a collection of integers, we want to find the longest arithmetic series that can be formed by choosing a sub-collection (possibly the entire collection). Create a class ASeries that contains a method longest that is given a series values and returns the length of the longest arithmetic series that can be formed from values.

Constraints
- Values will contain between 2 and 50 elements inclusive.
- Each element of values will be between -1,000,000 and 1,000,000 inclusive.
- Solution should NOT use a 2-dimensional array/matrix as the main data structure
- Need a method named longest which computes the longest Arithmetic Series given an array of integers (public int longest(int[] values))
- Class needs to be named ASeries
- Make sure to submit as a *.java file (Feel free to include anything else you might think necessary)

Examples
0)
{3,8,4,5,6,2,2}
Returns: 5
No arithmetic series using these values is longer than 2,3,4,5,6.

1)
{-1,-5,1,3}
Returns: 3
-1, 1, 3 is an arithmetic series (so is 3,-1,-5).

2)
{-10,-20,-10,-10}
Returns: 3
-10,-10,-10 is an arithmetic series.更多精彩文章及讨论，请光临枫下论坛 rolia.net

you can practice at topcoder.com and get familiar with this kind of questions -benbenli(大岭); 2016-2-8 (#9934246@0)

谢了，没时间看这些东西啊。 -unhappy_popular(unhappy_popular); 2016-2-8 (#9934275@0)

数学题而已。最长答案也就50。一个个试呗。只用加法。从最小的difference开始加。 -kakaka(小胖子); 2016-2-8 (#9934274@0) +1

你这样做面试题，立马废掉 -bbb333(ccc); 2016-2-10 (#9937661@0)

1.sort the list. 2. Then -iamflying(自食其水果); 2016-2-9 {487} (#9935295@0)
Longest seq must either contain the smallest or not contain the smallest.
a) contains the smallest: use for loop to go thru the rest of the list as the second number, you will get the leap size. Try to use this leap size to test how long the seq can go.
b) doesn't contain the smallest number: use tail recursive to go thru the rest of the list.

Worst time complicity: O(n^3). Average should be close to O(n^2) because the inner loop will end when the first missing number is found.

how to tell it contains the smallest or it doesn't contain the smallest? for example: list: {1, 31, 61, 2, 22, 42,62,82, 3, 13, 23,33} the longest list is 2, 22, 42,62,82, how to tell 1 is not in the list and 2 is in the list. -sxffff(lookingforjob); 2016-2-10 (#9936821@0)

我实现并不需要知道最小数是否在序列中，因为算法会分别对此计算。 -iamflying(自食其水果); 2016-2-10 {147} (#9936841@0)
case a 这个步骤计算最小的数在序列中，返回一个最大值。case b通过递归计算最小的数不在序列中的情况，返回一个最大值。最终结果就是case a, b中最大的数。

Java Implementation is here: -iamflying(自食其水果); 2016-2-10 {908} (#9937189@0) +2
public static int getMaxSeqSize(int... input) {
Arrays.sort(input);
int maxLen = 1;
int end = input.length - maxLen;
for (int first = 0; first < end; first++) {
for (int second = first + 1; second <= end; second++) {
int leap = input[second] - input[first];
int next = input[second] + leap;
int len = 2;
for (int i = second +1; i < input.length; i++) {
if (input[i] == next) {
len++;
next += leap;
} else if (input[i] > next) {
break;
}
}
if (len > maxLen) {
maxLen = len;
end = input.length - maxLen;
}
}
}
return maxLen;
}

xiang ni xuexi! ! me green hand in java, glad I'm getting the identical result. -mustang(mustang); 2016-2-10 (#9937493@0)
你的程序最坏是O(n^3)，平均也是O(n^3). 这个题O(n^2)可以解决。 -juanzhulian(UnlessYouShowMeHow); 2016-2-10 (#9937638@0)

Show us how to get O(n^2) -iamflying(自食其水果); 2016-2-10 (#9937715@0)

人多力量大，O(n^2) 写法下面楼主已经给了。 -juanzhulian(UnlessYouShowMeHow); 2016-2-10 (#9938383@0)

还有待商榷 (#9938404@0) -benbenli(大岭); 2016-2-10 (#9938405@0)
两重循环内的hashTable.get(diff)的worst case是O(n)。如果换成TreeMap，那就是O(log(n))，那也只能做到(n^2)Log(n)。 -iamflying(自食其水果); 2016-2-10 (#9938487@0)

要对java, c#的hash function有信心，In amortized case, hashmap的get()是O(1). 所以这题平均时间复杂度O(n^2). -juanzhulian(UnlessYouShowMeHow); 2016-2-11 (#9938555@0)

他的算法大致是O(n^4)，和hash function没关系。buildHashTable()生成的hash table的尺寸已经是n^2了，analyze() loop里又每次遍历n个数和可能n^2个pair。 -geekcode(文心雕码); 2016-2-11 {55} (#9938565@0)
虽然两个n^2不会同时出现，但是算法复杂度的量级不会减低。

您回贴快糙猛啊，n^4一出，别人很难跟你的贴。拜托花5分钟好好读一下人家的代码。我还是先潜水玩吧:-) 提个醒，hash function决定了那个get()最坏情况的O(n)有多大可能出现。 -juanzhulian(UnlessYouShowMeHow); 2016-2-11 (#9938575@0) +1

昨天没仔细看，是O(n^3)。key的size是n^2级, 不管怎么hash，也不会是n级。 -geekcode(文心雕码); 2016-2-11 (#9938600@0)

计算时间复杂度的Worst case依旧没有达到O(n^2)。倒是消耗的存储空间不少。 -iamflying(自食其水果); 2016-2-11 (#9938606@0)

- Solution should NOT use a 2-dimensional array/matrix as the main data structure -sxffff(lookingforjob); 2016-2-11 (#9938568@0)

不错，思路干净简洁。感觉平均不会close to O(n^2) ，可能会O(n^2*log(n))。我觉得应该有O(n^2)的算法，不过解释起来比较复杂，如果周末有空我会贴上来。 -geekcode(文心雕码); 2016-2-10 (#9938556@0)

我感觉楼主找出的O(n^2*log(n))的解法的时间复杂度算是最优了。但在面试中当场板书，除非已知该算法，否则我是写不出来。 -iamflying(自食其水果); 2016-2-11 (#9938616@0)

check this out -mustang(mustang); 2016-2-9 {197} (#9936192@0)
it's not that hard as it looks like:

1) sort;
2) calculate delta different between current element & its immediate predecessor
3) count the longest sequence with the same delta.

code here:
http://1drv.ms/1T4l44b

眼高手低的我来了。你的程序假定满足条件的序列,在拍好序的数组里是相邻的，这个好像不对。 1, 2, 6, 7, 11, 可以有1,6, 11满足条件吧。也可能我理解错了。 -juanzhulian(UnlessYouShowMeHow); 2016-2-9 (#9936717@0)

我的理解是： -mustang(mustang); 2016-2-9 {239} (#9936770@0)
在给出的一组数中，找出这样一组数，这组数的特点是，每后一个数减其相临前一个数的差，都是相等，题目要求找到最长的那组数的长度。

例如：　１　２　６　７　１１
结果可以是　１，２　（差是１）　or ６，７　（差也是１），　上面那段代码会返回２。

1,6,11 是3 个数，所以你的答案不对 -sxffff(lookingforjob); 2016-2-9 (#9936784@0)

你对了，俺错了。谢谢 -mustang(mustang); 2016-2-9 (#9936806@0)

thanks all who pointing out the issue with my code, here is revised one: 1,2,6,7,11 = > 1,6, 11 (5), new code here -mustang(mustang); 2016-2-10 {76} (#9937438@0)
key point : remember the start point & delta for maximum count sequence.

http://1drv.ms/1SIvF6D

大家讨论啥呢？不就是个双循环的事情？ -guestagain(guest again); 2016-2-10 (#9937306@0)
My two cents -kakashi(kakashi); 2016-2-10 {578} (#9937402@0)
1. sort
2.a create an ArrayList<ArrayList<Integer>> listOfSeries
2.b set maxLen = 0
3. Loop through the number list
for each number
3.1 Loop through the listOfSeries
for each series in the listOfSeries
If we can add the current number to the current series, add it. Set maxLen = +1
3.2 Add a new arrayList to the listOfSeries, this arrayList contains only the current number

Take {3,8,4,5,6,2,2} as example, then the final listOfSeries consists of:

,2,2
,2,3,4,5,6
,3,4,5,6
,4,5,6
,5,6
,6,8
,8
说的这么啰嗦，简单点，不就是找一个最长的等差数列嘛 -bbb333(ccc); 2016-2-10 (#9937664@0)
I wrote the code in C# (replaced leading spaces to dots to keep indentation). -benbenli(大岭); 2016-2-10 {4914} (#9937690@0) +1
本文发表在 rolia.net 枫下论坛I used only basic language elements and it should straightforward to convert to Java or C or C++ or any similar language. I also appended the output of the code. I believe this is the optimal code: space O(N) and time O(N^3) Hope it helps

using System;
using System.Text;

namespace ArithmeticSeriesQuiz
{
....class Program
....{
........static void Main(string[] args)
........{
............Resolve(new int[] { 3, 8, 4, 5, 6, 2, 2 });
............Resolve(new int[] { -1, -5, 1, 3 });
............Resolve(new int[] { -10, -20, -10, -10 });
........}

........public static void Resolve(int[] values)
........{
............Console.WriteLine("Question series: {0}", ASeries.ArrayToString(values));
............int[] resultSeries;
............int length = ASeries.Longest(values, out resultSeries);
............Console.WriteLine("Returns: {0}", length);
............Console.WriteLine("Result series: {0}", ASeries.ArrayToString(resultSeries));
............Console.WriteLine();
........}
....}

....public class ASeries
....{
........public static int Longest(int[] values, out int[] longestSeries)
........{
............int lengthOfLongestSeries = 0;
............longestSeries = null;

............if (values != null && values.Length > 0)
............{
................// Sort
................for (int i = 0; i < values.Length; ++i)
................{
....................for (int j = i + 1; j < values.Length; ++j)
....................{
........................if (values[i] > values[j])
........................{
............................int temp = values[i];
............................values[i] = values[j];
............................values[j] = temp;
........................}
....................}
................}

................int[] workingSeries = new int[values.Length];

................for (int firstElementIndex = 0; firstElementIndex < values.Length; ++firstElementIndex)
................{
....................workingSeries[0] = values[firstElementIndex];

....................for (int secondElementIndex = firstElementIndex + 1; secondElementIndex < values.Length; ++secondElementIndex)
....................{
........................workingSeries[1] = values[secondElementIndex];
........................int lengthOfWorkingSeries = 2;

........................int delta = values[secondElementIndex] - values[firstElementIndex];
........................int nextElementValue = values[secondElementIndex] + delta;

........................for (int nextAvailableElementIndex = secondElementIndex + 1; nextAvailableElementIndex < values.Length; ++nextAvailableElementIndex)
........................{
............................if (values[nextAvailableElementIndex] > nextElementValue)
............................{
................................break; // next value of the arithmetic series is not in the array. this series can not be longer
............................}

............................if (values[nextAvailableElementIndex] == nextElementValue)
............................{
................................// found the next value of the arithmetic series, save it
................................workingSeries[lengthOfWorkingSeries++] = values[nextAvailableElementIndex];
................................nextElementValue = values[nextAvailableElementIndex] + delta;
............................}
........................}

........................if (lengthOfWorkingSeries > lengthOfLongestSeries)
........................{
............................lengthOfLongestSeries = lengthOfWorkingSeries;
............................longestSeries = new int[lengthOfLongestSeries];
............................for (int i = 0; i < lengthOfLongestSeries; ++i)
............................{
................................longestSeries[i] = workingSeries[i];
............................}
........................}

....................}
................}
............}

............return lengthOfLongestSeries;
........}

........public static string ArrayToString(int[] values)
........{
............StringBuilder buffer = new StringBuilder();
............buffer.Append("[ ");

............if (values != null && values.Length > 0)
............{
................for (int i = 0; i < values.Length; ++i)
................{
....................buffer.Append(values[i]);
....................buffer.Append(", ");
................}

................buffer.Length -= 2; // remove the last delimeter
............}
............buffer.Append(" ]");

............return buffer.ToString();
........}
....}
}

// Output
Question series: [ 3, 8, 4, 5, 6, 2, 2 ]
Returns: 5
Result series: [ 2, 3, 4, 5, 6 ]

Question series: [ -1, -5, 1, 3 ]
Returns: 3
Result series: [ -5, -1, 3 ]

Question series: [ -10, -20, -10, -10 ]
Returns: 3
Result series: [ -10, -10, -10 ]更多精彩文章及讨论，请光临枫下论坛 rolia.net
首先谢谢各位的热心，没想到很多的高人，提供了不少的思路 -unhappy_popular(unhappy_popular); 2016-2-10 {4188} (#9937838@0)
本文发表在 rolia.net 枫下论坛我从网上找的了这道题的思路。下面是我的java code

是从下面这个链接的思路里，改写的。
http://codercareer.blogspot.ca/2014/03/no-53-longest-arithmetic-sequence.html

import java.io.Console;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class ASeries {

public int longest(int[] values) {

// sort the array
Arrays.sort(values);

Map<Integer, List<Pair>> hashTable = buildHashTable(values);

return analyze(hashTable, values.length);
}

/*

for an array {3, 8, 4, 5, 6, 2, 2}, group the pars like this
differenece 0: (2,2)
difference 1: (2,3), (3,4), (4,5),(5,6)

so we need a hash table to store the information, the key is the difference.
the value is the indexes of the pairs(not values)
*/
private Map<Integer, List<Pair>> buildHashTable(int[] values) {

Map<Integer, List<Pair>> hashTable = new HashMap<Integer, List<Pair>>();

for (int i = 0; i < values.length; i++) {
for (int j = i + 1; j < values.length; j++) {

Pair pair = new Pair();
pair.setFirst(i);
pair.setSecond(j);

int diff = values[j] - values[i];
if (hashTable.containsKey(diff)) {
hashTable.get(diff).add(pair);
} else {
List<Pair> newValue = new ArrayList<Pair>();
newValue.add(pair);
hashTable.put(diff, newValue);
}
}
}

return hashTable;

}

/*
in this method, we need to get the length of the pairs with each difference.

A list of pairs with difference k is got given a key k in the hash table.
If an element A[i] is mth element is an arithmetic sequence with a common difference k, and there is a pair (A[i], A[j]) (j>i) in the list of pairs,
the element A[j] should be the m+1th elemement in the arithmetic sequence.

*/
private int analyze(Map<Integer, List<Pair>> hashTable, int lengthOfNumbers) {

int maxLength = 0;
for (int key : hashTable.keySet()) {
int[] lengths = new int[lengthOfNumbers];

for (int i = 0; i < lengthOfNumbers; i++) {
lengths[i] = 1;
}

for (Pair pair : hashTable.get(key)) {
lengths[pair.getSecond()] = lengths[pair.getFirst()] + 1;
}

for (int length : lengths) {
if (length > maxLength) {
maxLength = length;
}
}
}

return maxLength;
}

private static void test(String testName, int[] numbers, int expected) {

ASeries as = new ASeries();

if (as.longest(numbers) == expected) {
System.out.println(String.format("%s passed.", testName));
} else {
System.out.println(String.format("%s failed.", testName));
}
}

private static void test1() {
int[] numbers = {3, 8, 4, 5, 6, 2, 2};
int expected = 5;
test("test1", numbers, expected);
}

private static void test2() {
int[] numbers = {-1, -5, 1, 3};
int expected = 3;
test("test2", numbers, expected);
}

private static void test3() {
int[] numbers = {-10, -20, -10, -10};
int expected = 3;
test("test3", numbers, expected);
}

public static void main(String[] args) {
test1();
test2();
test3();
}

}

class Pair {
private int first;
private int second;

public int getFirst() {
return first;
}

public void setFirst(int first) {
this.first = first;
}

public int getSecond() {
return second;
}

public void setSecond(int second) {
this.second = second;
}
}

不知道哪里有这样的活动，让我们这些在多伦多的IT猥琐男，每月聚一下，大家交流，交流啊？哪位大侠有这样振臂一呼的能力？更多精彩文章及讨论，请光临枫下论坛 rolia.net

I believe this implementation is too complicated for interview answer. Have a look at mine above which is simple and straightforward. -benbenli(大岭); 2016-2-10 (#9938208@0)

my code: -zhouziren1(zhouziren); 2016-2-10 {1375} (#9938278@0) +1
本文发表在 rolia.net 枫下论坛public class ASeries {
public static final int MIN_VALUES_LENGTH=2;
public static final int MAX_VALUES_LENGTH=50;
public static final int MIN_VALUE=-1000000;
public static final int MAX_VALUE=1000000;

public static void main(String[] args) throws Exception {
ASeries as=new ASeries();
System.out.println("res:"+as.longest(new int[] {3,8,4,5,6,2,2}));
}

public int longest(int[] values) throws Exception {
int ret=2;
if ( values == null || values.length < MIN_VALUES_LENGTH || values.length > MAX_VALUES_LENGTH ) {
throw(new Exception("values is null or has invalid amount of elements!"));
}
Arrays.sort(values);
if ( values[0] < MIN_VALUE || values[values.length-1] > MAX_VALUE ) {
throw(new Exception("At least one value is out of the range!"));
}
if ( values.length == 2 ) {
ret=2;
return ret;
}
int[] valuesDiff=new int[values.length-1];
for ( int i=1 ; i<values.length ; i++ ) {
valuesDiff[i-1]=values[i]-values[i-1];
}
int[] repeatCnt=new int[valuesDiff.length-1];
for ( int i=0 ; i<valuesDiff.length-1 ; i++ ) {
int tmpCount=1;
for ( int j=i+1 ; j<valuesDiff.length ; j++ ) {
if ( valuesDiff[j] == valuesDiff[i] ) {
tmpCount++;
}
}
repeatCnt[i]=tmpCount;
}
Arrays.sort(repeatCnt);
ret=repeatCnt[repeatCnt.length-1]+1;
return ret;
}

}更多精彩文章及讨论，请光临枫下论坛 rolia.net

我的代码对这组数结果是6，但是你的是5. 其实我很惊讶O(N^2)能算出来。Question series: [ 2, 2, 4, 5, 6, 8, 10, 12 ] Returns: 6 Result series: [ 2, 4, 6, 8, 10, 12 ] -benbenli(大岭); 2016-2-10 (#9938404@0)

没什么好惊讶的，这就是错误的解决方案，前面讨论过了。 -iamflying(自食其水果); 2016-2-10 (#9938478@0)

我看读了好几遍，不还是不理解为什么最大长度最后还要加1： ret = repeatCnt[repeatCnt.Length - 1] + 1; -benbenli(大岭); 2016-2-10 (#9938448@0)
1, 2, 6, 7, 11, 可以有1,6, 11满足条件吧。 -juanzhulian(UnlessYouShowMeHow); 2-9 (#9936717@0) -geekcode(文心雕码); 2016-2-11 (#9938567@0)

有论文： -sxffff(lookingforjob); 2016-2-11 (#9938578@0)
试试这个办法？ -zhengy4(zhengy4); 2016-3-29 {453} (#10017807@0)
先排序，然后用二分法，给每一个部分里面数列最长到最短的进行排序。
然后是merge, merge中把左子集和右子集已有的相差距离数列相加然后再统计一下从最多到最少就不用说了，必须做的，最关键的是要把大于子数列距离的数距离都要统计一边，当然这些新出现的距离是“最少的”因为才出现了1次么，但这个是这里的关键，否则会漏掉有可能会成为最长数列的距离，这一步有O(k^2)。

二分法是O(nlogn),但是merge用了O(k^2), 所以有可能会变成 O(n2) O(n^2logn) O(n^3),我没算啊，错了别骂我。

@Florida

I wrote the code in C# (replaced leading spaces to dots to keep indentation).

Replies, comments and Discussions:

More Topics