blob: 8ecd2e058ce615cc4b181e7ce32b9b3c6cb2c1bc (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
namespace ch_1;
public static class Ch1
{
public static void Main(string[] args)
{
// Call whichever implementation you'd like to use.
PrintThirdMax_impl2(args);
}
private static void PrintThirdMax_impl1(string[] args)
{
var firstThree = args.Select(int.Parse)
.OrderDescending().Distinct()
.Take(3).ToArray();
Console.WriteLine(
firstThree.Length >= 3 ? firstThree[2] :
firstThree.Length > 0 ? firstThree[0] :
""
);
}
private static void PrintThirdMax_impl2(string[] args)
{
var firstThree = args.Select(int.Parse).Max3().ToArray();
Console.WriteLine(
firstThree.Length >= 3 ? firstThree[2] :
firstThree.Length > 0 ? firstThree[0] :
""
);
}
private static IEnumerable<T> Distinct<T>(this IOrderedEnumerable<T> source)
{
using var enumerator = source.GetEnumerator();
if (!enumerator.MoveNext()) yield break;
var comparer = EqualityComparer<T>.Default;
var current = enumerator.Current;
yield return current;
while (enumerator.MoveNext())
{
var next = enumerator.Current;
if (comparer.Equals(current, next)) continue;
current = next;
yield return current;
}
}
/// <summary>Return the top 3 unique maximum integers in O(n) time.</summary>
private static IEnumerable<T> Max3<T>(this IEnumerable<T> source)
{
const int numMaxValues = 3;
var comparer = Comparer<T>.Default;
var maxValues = new List<T>();
foreach (var value in source) InsertIfNewMax(value);
return maxValues;
void InsertIfNewMax(T value)
{
for (var i = 0; i < numMaxValues; i++)
{
if (i < maxValues.Count && comparer.Compare(value, maxValues[i]) == 0) break;
if (i < maxValues.Count && comparer.Compare(value, maxValues[i]) <= 0) continue;
maxValues.Insert(i, value);
if (maxValues.Count > numMaxValues) maxValues.RemoveAt(numMaxValues);
break;
}
}
}
}
|
