一组无序的整数找出出现次数大于一半的数字

一、毫不犹豫,直接上Linq
            var list = new List { 1, 2, 3, 4, 1, 3, 6, 3, 4, 3, 3, 3, 3 };

            var result = list
                .GroupBy(m => m)
                .OrderByDescending(m => m.Count())
                .Select(p => p.Key)
                .First();

            Console.WriteLine($"{result}");
在面试过程,如果写出这样子算法,面试官肯定是不满意。?二、类似标记算法我们在遍历数组的时候可以用两个变量,一个cand用来保存遍历到当前数组的数字;另外一个变量times是用来记录当前数字出现的次数;在遍历第一个数的时候将times初始化为0,cand初始赋值为第一个数;接下来遍历数组1、如果下一个数字与cand当前保存的数相同则times+12、如果下一个数字与cand当前保存的数字不同则times-13、当times为0的时候,cand需要重新被赋值为下一个数,times被重新赋值为1,一直到遍历结束;下面举个例子,比如有一个数组{0,1,2,1,1},按照上面的算法思想,步骤如下1、开始的时候cand先被赋值为0,times为12、遍历到下一个数,1与cand不同,则times-1为0,;又times为0,则cand又被重新赋值为0,times又被重新赋值为03、同样的道理,遍历下一个数字,2与cand不同,则times-1为0;又times为0,则cand又被重新赋值为2,times又被重新赋值为14、继续遍历下一个数字,1与cand不同,则times-1为0;又times为0,则cand被赋值为1,times为15、继续遍历,1与cand相同,times+1,times为2;最后我们返回的就是将times设为2的cand
//算法2,类似标记算法
            var times = 0;
            var temp = list[0];
            foreach (var item in list)
            {
                if (times == 0)
                {
                    temp = item;
                    times = 1;
                }
                else
                {
                    if (item == temp)
                    {
                        times++;
                    }
                    else
                    {
                        times--;
                        temp = item;
                    }
                }
            }
            Console.WriteLine($"{temp}");
  ?  

相关内容推荐