主元素1

发表于   |   分类于 ，   |  

主元素1

主元素的定义

给定一个整型数组，找出主元素，它在数组中的出现次数严格大于数组元素个数的二分之一。

例：给出数组[1,1,1,1,2,2,2]，其主元素为1

解法一

由于主元素的特性是主元素出现的次数比所有非主元素出现的次数和都多，因此可以用抵消法，两两元素抵消，若主元素与非主元素抵消，则主元素次数仍然多于非主元素之和，若两个不同的非主元素抵消，则对主元素出现次数最多无影响，若某一元素与主元素的值相等，则增加计数，否则减少计数。

设置初始主元素为第一个元素，遍历数组，如果下一个元素的值与主元素相同，则对主元素出现次数加一。若该元素与主元素不相等，则对主元素出现次数减一。直到主元素出现次数为0，则意味着主元素抵消了相同数量的非主元素。此时设置下一个元素为主元素，直到遍历结束。

时间复杂度：O(n)

空间复杂度：O(1)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int getMajorElementOfArray(int[] array) {
    int res = Integer.MIN_VALUE;
    if (ArrayUtils.isEmpty(array)) {
          return res;
    }
    int count = 1;
    res = array[0];
    for (int i = 1; i < array.length; ++i) {
        if (array[i] == res) {
            count++;
        } else {
            count--;
        }
        if (count == 0 && i < array.length-1) {
            res = array[i+1];
            count = 1;
            i++;
        } else if (count == 0 && i == array.length-1) {
            return Integer.MIN_VALUE;
        }
    }
    return res;
}

解法二

同样是抵消法，对数组相邻对两个元素判断，如果相等，则用新数组保存这个元素，用于下一次判断；否则抵消，此时主元素数量还是多于非主元素数量之和。

时间复杂度：O(log(n))

空间复杂度：O(n)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int getMajorElementOfArrayRecursively(int[] array, int length) {
    if (length == 1) {
        return array[0];
    }
    int[] newArray = new int[length/2 + 1];
    int j = 0;
    for (int i = 0; i < length; i += 2) {
        if (i + 1 < length && array[i] == array[i + 1]) {
            newArray[j++] = array[i];
        } else if (i + 1 == length) {
            newArray[j++] = array[i];
        }
    }
    return getMajorElementOfArrayRecursively(newArray, j);
}