高效遍历整数数组：士兵层级计数算法优化求助

测试用例 #

用例1 #

给定数组ranks = [3,4,3,0,2,2,3,0,0]，函数应返回5，原因如下：

• 3名军衔为3的士兵（ranks[0]、ranks[2]、ranks[6]）可向军衔为4的士兵（ranks[1]）汇报
• 2名军衔为2的士兵可向任意军衔为3的士兵汇报

用例2 #

给定数组ranks = [4,2,0]，函数应返回0。

用例3 #

给定数组ranks = [4,4,3,3,1,0]，函数应返回3，原因如下：

• 1名军衔为0的士兵可向军衔为1的士兵汇报
• 2名军衔为3的士兵可向任意军衔为4的士兵汇报

任务要求 #

编写高效算法，满足以下假设：

• N为[2, 100000]范围内的整数
• ranks数组的每个元素为[0, 1000000000]范围内的整数

现有实现代码 #

namespace Test
{
    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;
        }
    }
}

现有方案的问题 #

当前实现采用双层循环，时间复杂度为O(n²)，当n达到100000时，计算量会呈指数级增长，直接触发超时，完全无法满足性能要求。你提到尝试过排序但没提升效率，大概率是排序后仍采用了低效的遍历逻辑，没有利用排序后的结构简化计算。

优化思路 #

核心逻辑是通过统计军衔频次来避免重复遍历，将时间复杂度降至O(n)，具体步骤如下：

1. 统计军衔人数：遍历一次数组，用哈希表（如C#的Dictionary<int, int>）记录每个军衔对应的士兵数量，这一步时间复杂度为O(n)。
2. 计算有效汇报数：遍历哈希表中的每个军衔r，如果哈希表中存在r+1这个军衔，说明所有军衔为r的士兵都能找到汇报对象，直接将r对应的人数加到结果中。

优化后代码示例 #

class Solution
{
    public int solution(int[] ranks)
    {
        Dictionary<int, int> rankCount = new Dictionary<int, int>();
        // 统计每个军衔的士兵数量
        foreach (int r in ranks)
        {
            if (rankCount.ContainsKey(r))
                rankCount[r]++;
            else
                rankCount[r] = 1;
        }
        
        int result = 0;
        // 遍历所有军衔，检查是否存在高一级的军衔
        foreach (var pair in rankCount)
        {
            if (rankCount.ContainsKey(pair.Key + 1))
                result += pair.Value;
        }
        
        return result;
    }
}

这个实现中，哈希表的插入和查找操作平均时间复杂度为O(1)，两次线性遍历总时间复杂度为O(n)，完全能处理n=100000的大规模输入。

内容的提问来源于stack exchange，提问作者Graham Schwardt