Goal In the army, each soldier has an assigned rank. A soldier of rank X has to report to (any) soldier of rank X 1. Many soldiers can report to the same superior. Given an array ranks consisting of soldiers ranks, returns the number of soldiers who can report to some superior.
Test Cases
Case 1 Given ranks[3,4,3,0,2,2,3,0,0], your function should return 5, because :
- Three soldiers of rank 3 (ranks[0], ranks[2], ranks[6]) may report to a soldier of rank 4 (ranks[1])
- Two soldiers of rank 2 may report to any soldier of rank 3
Case 2 Given ranks[4,2,0], your function should return 0.
Case 3 Given ranks[4,4,3,3,1,0], your function should return 3, because :
- A soldier of rank 0 can report to a soldier of rank 1
- Two soldiers of rank 3 can report to any soldier of rank 4
Task Write an efficient algorithm for the following assumptions :
- N is an integer within the range [2.. 100,000]
- Each element of array ranks is an integer within the range [0.. 1,000,000,000]
namespace Army
{
class Program
{
static void Main(string[] args)
{
var rand = new Random();
var ranks = new int[][]
{
new int[]{ 3, 4, 3, 0, 2, 2, 3, 0, 0}, // 5
new int[]{ 3, 3, 3, 4, 2, 2, 3, 1, 1 }, // 8
new int[]{4 , 2, 0}, // 0
new int[]{4, 4, 3, 3, 1, 0}, // 3
new int[]{1,2,3,4,5}, // 4
new int[]{0,2,4}, // 0
new int[]{1,1,1,1,1,1, 3,2, 2, 1}, // 9
// Enumerable.Range(1,100000).ToList().Select(a => rand.Next(1000000000)).ToArray()
};
var solver = new Solution();
foreach (var test in ranks)
{
var result = solver.solution(test);
Console.WriteLine($"Result: {result}");
}
Console.ReadKey();
}
}
class Solution
{
public int solution(int[] ranks)
{
int count = 0;
// First ranks traversal
for (int x = 0; x < ranks.Length; x )
{
foreach(int yrank in ranks)
{
if (ranks[x] == yrank) continue;
if (ranks[x] 1 == yrank)
{
// if x 1 is present
count = 1;
break;
}
}
}
return count;
}
}
}
My solution is working for simple test cases but it's not at all an efficient solution. I'm sure I can simplify greatly the problem and not having two loops which give us a time complexity of at least O(n^2). I'm sure this problem can be simplified up to a time complexity of O(logN) or maybe something better but I can't see how... I thought of sorting the ranks array first but it's not more efficient.
***Could you please give me some help on this kind of problem or tell me what I did wrong in my approach ? Thank you.
CodePudding user response：
I took your model and migrated it to a BenchmarkDotNet project:
Below is the code.
Solution1 is a copy of yours. Solution2 is an alternative. Solution3 is copied from a poster who posted an answer before me.
You can add as many solutions as you like and see how they perform.
Spoiler, here are the results:
| Method | Mean | Error | StdDev | Rank | Gen0 | Gen1 | Allocated |
|---|---|---|---|---|---|---|---|
| Solution3 | 1.659 ms | 0.0259 ms | 0.0217 ms | 1 | 21.4844 | 1.9531 | 97473 B |
| Solution2 | 10.284 ms | 0.1994 ms | 0.2134 ms | 2 | - | - | 8 B |
| Solution1 | 68.283 ms | 0.6395 ms | 0.6281 ms | 3 | - | - | 120 B |
As you can see, Solution2 is much faster with less resource allocation and Solution3 is 5X faster still, but with more memory allocation and a bit of garbage collection (Gen0 and Gen1).
I'll leave it to you to judge speed vs. memory allocation, but a benchmarking tool like this one will help you best judge different ideas if the comparisons are fair.
[MemoryDiagnoser]
[Orderer(SummaryOrderPolicy.FastestToSlowest)]
[RankColumn]
public class ListTraversal
{
//private static int[][] data = Array.Empty<int[]>();
private static int[] ranks = Array.Empty<int>();
[GlobalSetup]
public void Setup()
{
var rand = new Random();
//ranks = new int[] { 3, 4, 3, 0, 2, 2, 3, 0, 0 }; // 5;
ranks = Enumerable.Range(1, 100000).ToList().Select(a => rand.Next(0, 1000)).ToArray();
// data = new int[][] {
// new int[]{ 3, 4, 3, 0, 2, 2, 3, 0, 0}, // 5
// new int[]{ 3, 3, 3, 4, 2, 2, 3, 1, 1 }, // 8
// new int[]{4 , 2, 0}, // 0
// new int[]{4, 4, 3, 3, 1, 0}, // 3
// new int[]{1,2,3,4,5}, // 4
// new int[]{0,2,4}, // 0
// new int[]{1,1,1,1,1,1, 3,2, 2, 1}, // 9
//// Enumerable.Range(1,100000).ToList().Select(a => rand.Next(1000000000)).ToArray()
//};
}
[Benchmark]
public void Solution1()
{
int count = 0;
// First ranks traversal
for (int x = 0; x < ranks.Length; x )
{
foreach (int yrank in ranks)
{
if (ranks[x] == yrank) continue;
if (ranks[x] 1 == yrank)
{
// if x 1 is present
count = 1;
break;
}
}
}
}
[Benchmark]
public void Solution2()
{
int count = 0;
ReadOnlySpan<int> copy = new ReadOnlySpan<int>(ranks);
// First ranks traversal
for (int x = 0; x < ranks.Length; x )
{
count = (copy.Contains(ranks[x] 1))
? 1
: 0;
}
}
[Benchmark]
public void Solution3()
{
var count = 0;
var map = new Dictionary<int, int>();
foreach (var rank in ranks)
map[rank] = map.ContainsKey(rank) ? map[rank] 1 : 1;
var sorted = map.OrderBy(x => x.Key).ToList();
for (int i = 0; i < sorted.Count - 1; i )
if (sorted[i].Key 1 == sorted[i 1].Key)
count = sorted[i].Value;
}
}
My Program.cs is simply:
using BenchmarkDotNet.Running;
BenchmarkRunner.Run<ListTraversal>();
CodePudding user response：
My solution is O(nlogn) in the worst case scenario. An average complexity have to be better, because I sort unique ranks not all ranks
public int solution(int[] ranks)
{
var count = 0;
var map = new Dictionary<int, int>();
foreach (var rank in ranks)
map[rank] = map.ContainsKey(rank) ? map[rank] 1 : 1;
var sorted = map.OrderBy(x => x.Key).ToList();
for (int i = 0; i < sorted.Count - 1; i )
if (sorted[i].Key 1 == sorted[i 1].Key)
count = sorted[i].Value;
return count;
}
UPDATE: new version has O(n) complexity! (but it can be hard to understand :)).
public int solution1(int[] ranks)
{
var count = 0;
var map = new Dictionary<int, int>();
// O(n)
foreach (var rank in ranks)
{
if (!map.ContainsKey(rank))
map[rank] = -2;
else
{
var sign = map[rank] >= 0 ? 1 : -1;
map[rank] = map[rank] 1 * sign;
}
if (!map.ContainsKey(rank - 1))
map[rank - 1] = 1;
else
map[rank - 1] = Math.Abs(map[rank - 1]);
}
foreach (var item in map)
if(item.Value > 1)
count = item.Value - 1;
return count;
}