- 相关推荐
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