- 相關(guān)推薦
2016大眾點(diǎn)評研發(fā)工程師筆試題
N個未排序的整數(shù)，在線性時(shí)間內(nèi)，求這N個整數(shù)在數(shù)軸上相鄰兩個數(shù)之間的最大差值(請寫出關(guān)鍵算法)
相關(guān)解答：
【一】
easy，以(max-min) / n 分N個桶，每個桶只保存最小值和最大值，這樣就相當(dāng)于排完序了
然后在就最多比較桶內(nèi)和桶間就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);
}
}
}
完美輸出兩兩的差值
【三】
看了前面幾位的評論，審題不仔細(xì)或者不明白線性的意思。用排序的話肯定是不對的，排序最快的是NlogN也是非線性的。
這題目不難重要的理解題目的意思。下面給出Java的實(shí)現(xiàn)。
/**
* 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;
}
【大眾點(diǎn)評研發(fā)工程師筆試題】相關(guān)文章：
大眾點(diǎn)評CEO張濤的創(chuàng)業(yè)故事12-25
研發(fā)工程師求職簡歷01-24
百度技術(shù)研發(fā)類筆試題09-26
設(shè)計(jì)研發(fā)工程師崗位職責(zé)06-15
研發(fā)工程師簡歷表格模板08-10
研發(fā)工程師求職簡歷6篇01-24