我有一個list<int> input = //from db of one million records的百萬記錄。盡管我知道使用input.OrderByDescending().Skip(1).Take(1)可以解決問題，但是如果我有一百萬條記錄，則不是最佳做法OrderBY。在這種情況下，當我們有更多記錄時，哪種解決方案是最佳解決方案？
3 回答
jeck貓
TA貢獻1909條經驗 獲得超7個贊
瀏覽列表，同時跟蹤max，以及max2，你會得到O(N)與O(N * log(N))時間復雜度：
// Maximum value
int max = Math.Max(input[input.Count - 1], input[input.Count - 2]);
// Second greatest
int max2 = Math.Min(input[input.Count - 1], input[input.Count - 2]);
// i >= 0: Comparing with 0 is slightly faster then with Count
for (int i = input.Count - 3; i >= 0; --i) {
int v = input[i];
if (v >= max) {
max2 = max;
max = v;
}
else if (v > max2)
max2 = v;
}
編輯：如果重復項應被忽略（請參見下面的評論），則答案[1, 2, 3, 4, 4, 4, 4]應為3，而不是4：
// Maximum value
int max = int.MinValue;
// Second greatest
int max2 = int.MinValue;
// i >= 0: Comparing with 0 is slightly faster then with Count
for (int i = input.Count - 1; i >= 0; --i) {
int v = input[i];
if (v > max) {
max2 = max;
max = v;
}
else if (v > max2 && v != max)
max2 = v;
}
慕尼黑的夜晚無繁華
TA貢獻1864條經驗 獲得超6個贊
您可以通過跟蹤下一個最大值并在列表中進行一次迭代來做到這一點。
int max = Int32.MinValue;
int nextMax = Int32.MinValue;
for(int i=0; i<list.Count(); i++)
{
if(list[i] > max)
{
nextMax = max;
max = list[i];
}
else if(list[i] > nextMax)
{
nextMax = list[i];
}
}
絕地無雙
TA貢獻1946條經驗 獲得超4個贊
這是一個僅使用LINQ和C＃7元組迭代一次的解決方案：
var input = Enumerable.Range(0, 101);
var topTwo = input.Aggregate((Biggest: Int32.MinValue, SecondBiggest: Int32.MinValue),
(acc, next) =>
{
if (next > acc.Biggest)
{
acc.SecondBiggest = acc.Biggest;
acc.Biggest = next;
}
if (next < acc.Biggest && next > acc.SecondBiggest)
acc.SecondBiggest = next;
return acc;
});
WriteLine(topTwo.SecondBiggest); // 99
- 3 回答
- 0 關注
- 247 瀏覽
添加回答
舉報
0/150
提交
取消