整数溢出问题c语言笔试题（剑指offergo面试题39）
整数溢出问题c语言笔试题（剑指offergo面试题39）func majorityElement(nums []int) int { result count := 0 0 for i := 0; i < len(nums); i { if count == 0 { result = nums[i] count } else if result == nums[i] { count } else { count-- } } return result }4、位运算；时间复杂度O(n)，空间复杂度O(1)func majorityElement(nums []int) int { m := make(map[int]int) result := 0 for _ v := range nums { if _ ok := m[v]; ok { m[v]
题目数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:输入: [1 2 3 2 2 2 5 4 2] 输出: 2
限制：1 <= 数组长度 <= 50000
注意：本题与主站 169 题相同
解题思路分析1、排序后取半；时间复杂度O(nlog(n))，空间复杂度O(1)
func majorityElement(nums []int) int {
sort.Ints(nums)
return nums[len(nums)/2]
}
2、哈希法；时间复杂度O(n)，空间复杂度O(n)
func majorityElement(nums []int) int {
m := make(map[int]int)
result := 0
for _ v := range nums {
if _ ok := m[v]; ok {
m[v]
} else {
m[v] = 1
}
if m[v] > (len(nums) / 2) {
result = v
}
}
return result
}
3、Boyer-Moore投票算法；时间复杂度O(n)，空间复杂度O(1)
func majorityElement(nums []int) int {
result count := 0 0
for i := 0; i < len(nums); i {
if count == 0 {
result = nums[i]
count
} else if result == nums[i] {
count
} else {
count--
}
}
return result
}
4、位运算；时间复杂度O(n)，空间复杂度O(1)
func majorityElement(nums []int) int {
if len(nums) == 1 {
return nums[0]
}
result := int32(0)
// 64位有坑
mask := int32(1)
for i := 0; i < 32; i {
count := 0
for j := 0; j < len(nums); j {
if mask&int32(nums[j]) == mask {
count
}
}
if count > len(nums)/2 {
result = result | mask
}
mask = mask << 1
}
return int(result)
}
5、分治法；时间复杂度O(nlog(n))，空间复杂度O(log(n))
func majorityElement(nums []int) int {
return majority(nums 0 len(nums)-1)
}
func count(nums []int target int start int end int) int {
countNum := 0
for i := start; i <= end; i {
if nums[i] == target {
countNum
}
}
return countNum
}
func majority(nums []int start end int) int {
if start == end {
return nums[start]
}
mid := (start end) / 2
left := majority(nums start mid)
right := majority(nums mid 1 end)
if left == right {
return left
}
leftCount := count(nums left start end)
rightCount := count(nums right start end)
if leftCount > rightCount {
return left
}
return right
}总结
Easy题目， 同leetcode169_多数元素多种方法都可以解决问题，可以研究一下Boyer-Moore算法
