LeetCode Majority Element -电脑资料

电脑资料 时间:2019-01-01 我要投稿
【meiwen.anslib.com - 电脑资料】

    Majority Element

    Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

    You may assume that the array is non-empty and the majority element always exist in the array.

    Credits:

    Special thanks to @ts for adding this problem and creating all test cases.

    找出出现次数大于数组1/2 长度次的数字,

LeetCode Majority Element

    思路:

    本题解法很多:

    1.排序后判断第n/2个元素与首元素是否相等

    2.哈希表

    3.每次移除两个不等的元素

    ...

    第3种方法最快,在实际应用中,哪种方式的时间复杂度都是可以接受的,这里的实现使用了第二种,即借助哈希表来完成统计,

电脑资料

LeetCode Majority Element》(http://meiwen.anslib.com)。

    实现代码:

   

public class Solution {    public int MajorityElement(int[] nums) {        if(nums.Length == 0){    		return 0;    	}    	    	var hash = new Dictionary<int, int="">();    	var max = 1;    	var maxKey = nums[0];    	for(var i = 0;i < nums.Length; i++){    		if(hash.ContainsKey(nums[i])){    			hash[nums[i]] ++;    			if(max < hash[nums[i]]){    				max = hash[nums[i]];    				maxKey = nums[i];    			}    		}    		else{    			hash.Add(nums[i],1);    		}    	}    	    	return maxKey;    }}</int,>

最新文章