题目

https://leetcode.cn/problems/majority-element/description/?envType=study-plan-v2&envId=top-interview-150 (opens new window)

多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

自解

思路分析

orz 真没想到简单题做的这么复杂……

1. 根据原数组长度，创建一个相同长度的复制数组，一个变长的去重数组存储第一次出现不同的值
2. 遍历原数组，去重列表不包含值（第一次出现不一样的值），复制数组在该值位置+1，后面出现这个值了该位置为0
3. 最后遍历复制数组，返回最大值index，最后原数组[index]

代码实现

func main() {
  arr := []int{1, 2, 2, 3}
  value := majorityElement(arr)
  fmt.Println(value)
}

func majorityElement(nums []int) int {
  l := len(nums)
  if l == 1 {
    return nums[0]
  }

  s1 := make([]int, l)
  s2 := make([]int, l)

  for i, v := range nums {
    index, ok := isExist(v, s2)
    if ok {
      s1[index] += 1
    } else {
      s1[i] += 1
      s2[i] = v
    }
  }

  maxIndex := 0
  temp := 0

  for i, v := range s1 {
    if v > temp {
      temp = v
      maxIndex = i
    }
  }

  return nums[maxIndex]
}

func isExist(target int, nums []int) (int, bool) {
  for i, v := range nums {
    if v == target {
      return i, true
    }
  }
  return -1, false
}

他解1

思路分析

1. 先排序
2. 处于中间的数就是出现次数最多的

代码实现

func majorityElement(nums []int) int {
    length := len(nums)
    sort.Ints(nums)
    return nums[length/2]
}

他解2

思路分析

摩尔投票法又称多数投票法，主要用于解决一个数组中的众数的问题。

根据上述的算法思想，我们遍历投票数组，将当前票数最多的候选人与其获得的（抵消后）票数分别存储在 major 与 count 中。

当我们遍历下一个选票时，判断当前 count 是否为零：

• 若 count == 0，代表当前 major 空缺，直接将当前候选人赋值给 major，并令 count++
• 若 count != 0，代表当前 major 的票数未被完全抵消，因此令 count--，即使用当前候选人的票数抵消 major 的票数

代码实现

func majorityElement(nums []int) int {
    major := 0
    count := 0

    for _, num := range nums {
        if count == 0 {
            major = num
        }
        if major == num {
            count += 1
        } else {
            count -= 1
        }
    }
    
    return major
}