[LeetCode]--169. 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 e

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.

给大家提供一个很nice的方法,因为题目有一点,多的数一定是占全部数的二分之一以上,所以遇到不同的就消除呗。剩下的绝对是那个大多数的数。

public int majorityElement(int[] nums) {
        int temp = 0, count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (count == 0) {
                temp = nums[i];
                count++;
            } else if (temp == nums[i])
                count++;
            else
                count--;
        }
        return temp;
    }

最开始的两个小程序也贴上来吧,虽然都超时了,但是代码逻辑都是对的。

蛮力法

public int majorityElement(int[] nums) {
        if (nums.length == 0)
            return 0;
        int sum = 0;
        int max = 0, temp = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++)
                if (nums[i] == nums[j])
                    sum++;
            if (sum > max) {
                temp = i;
                max = sum;
            }
            sum = 0;
        }
        return nums[temp];
    }

稍微改进一点点,但是还是超时了的普通算法。

public int majorityElement(int[] nums) {
        if (nums.length == 0)
            return 0;
        int[] flag = new int[nums.length];
        Arrays.fill(flag, 0);
        for (int i = 0; i < nums.length - 1; i++) {
            if (flag[i] != 0)
                continue;
            for (int j = i + 1; j < nums.length; j++) {
                if (flag[j] != 0)
                    continue;
                if (nums[i] != nums[j]) {
                    flag[i] = 1;
                    flag[j] = 1;
                    break;
                }
            }
        }
        for (int i = 0; i < flag.length; i++) {
            if (flag[i] != 1) {
                return nums[i];
            }
        }
        return 0;
    }
目录
相关文章
|
7月前
Leetcode 230. Kth Smallest Element in a BST
先来看下二叉搜索树的性质,对于任意一个非叶子节点,它的左子树中所有的值必定小于这个节点的val,右子树中所有的值必定大于或等于当前节点的val。 这条性质就保证了如果我们对二叉搜索树做中序遍历,中序遍历的结果肯定是有序的。对于此题而言,我们只需要拿到中序遍历结果,然后返回第k个即可,时间复杂度是O(n)。
48 1
|
Python
LeetCode 378. Kth S Element in a Sorted Matrix
给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。 请注意,它是排序后的第k小元素,而不是第k个元素。
82 0
LeetCode 378. Kth S Element in a Sorted Matrix
|
算法
LeetCode 229. Majority Element II
给定一个大小为 n 的数组,找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。 说明: 要求算法的时间复杂度为 O(n),空间复杂度为 O(1)。
63 0
LeetCode 229. Majority Element II
|
索引
LeetCode 162. Find Peak Element
给定一个输入数组 nums,其中 nums[i] ≠ nums[i+1],找到峰值元素并返回其索引。 数组可能包含多个峰值,在这种情况下,返回任何一个峰值所在位置即可。
80 0
LeetCode 162. Find Peak Element
|
算法 Python
LeetCode 169. 多数元素 Majority Element
LeetCode 169. 多数元素 Majority Element
|
Java C++
LeetCode之Remove Element
LeetCode之Remove Element
90 0
LeetCode之Next Greater Element I
LeetCode之Next Greater Element I
64 0
|
算法 Java
LeetCode 229 Majority Element II(主要元素II)(Array)(Boyer–Moore majority vote algorithm)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/52356817 原文 给定一个长度为n的整型数组,找出所有出现超过 ⌊ n/3 ⌋ 次的元素。
1010 0
|
容器
LeetCode 169 Majority Element(主要元素)(vector、map)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50504698 翻译 给定一个长度为n的数组,找出主要的元素。
788 0
|
10天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题