2016大眾點評研發工程師筆試題

　　N個未排序的整數，在線性時間內，求這N個整數在數軸上相鄰兩個數之間的最大差值(請寫出關鍵算法)

　　相關解答：

　　【一】

　　easy，以(max-min) / n　分N個桶，每個桶只保存最小值和最大值，這樣就相當于排完序了

　　然后在就最多比較桶內和桶間就ok了，最多2n次

　　【二】

　　private void Test(int[] randomNum)

　　{

　　Dictionary dic = new Dictionary();

　　for (int i = 0; i < randomNum.Length-1;i++ )

　　{

　　int dif = Mathf.Abs(randomNum[i] - randomNum[i + 1]);

　　dic.Add(i, dif);

　　}

　　Debug.LogError(dic.Count);

　　SortNum(dic);

　　}

　　private void SortNum(Dictionary dic)

　　{

　　int[] randomNum = new int[dic.Count];

　　int i = 0;

　　foreach(KeyValuePair num in dic)

　　{

　　randomNum[i] = num.Value;

　　i++;

　　}

　　for (int k = 0; k < randomNum.Length - 1;k++ )

　　{

　　for (int j = 0; j randomNum[j + 1])

　　{

　　int temp = 0;

　　temp = randomNum[j];

　　randomNum[j] = randomNum[j + 1];

　　randomNum[j + 1] = temp;

　　}

　　}

　　}

　　foreach (KeyValuePair num in dic)

　　{

　　if (dic.ContainsValue(randomNum[dic.Count - 1]))

　　{

　　Debug.Log(num.Value);

　　}

　　}

　　}

　　完美輸出兩兩的差值

　　【三】

　　看了前面幾位的評論，審題不仔細或者不明白線性的意思。用排序的話肯定是不對的，排序最快的是NlogN也是非線性的。

　　這題目不難重要的理解題目的意思。下面給出Java的實現。

　　/**

　　* Get largest absolute value between two neighbor element.

　　* Time consume T = (n - 1) and is linear.

　　* @param values

　　* @return largestABSValue

　　*/

　　private int getLargestABSValue (int[] values) {

　　int largestABSValue = 0;

　　int curABSValue = 0;

　　// return if values is empty or can't compare

　　if (null == values || 0 == values.length || 1== values.length)

　　return -1;

　　for (int i=0 ; i largestABSValue)

　　largestABSValue = curABSValue;

　　}

　　return largestABSValue;

　　}

【大眾點評研發工程師筆試題】相關文章：

大眾點評CEO張濤的創業故事12-25

研發工程師求職簡歷01-24

2016年蘭州中考各科目試題點評09-26

2015年北京高考理綜試題點評09-26

百度技術研發類筆試題09-26

設計研發工程師崗位職責06-15

研發工程師簡歷表格模板08-10

研發工程師求職簡歷6篇01-24

2016年北京高考語文試題點評:“鞏固”與“發展”結合09-26

音頻系統研發工程師簡歷模板09-25