Golang每日一练(leetDay0060) 多数元素、两数之和III

2023-05-29 168

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Golang每日一练(leetDay0060) 多数元素、两数之和III

169. 多数元素 Majority Element

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：[3,2,3]

输出：3

示例 2：

输入：[2,2,1,1,1,2,2]

输出：2

进阶：

尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

代码1： 哈希表

package main
import "fmt"
func majorityElement(nums []int) int {
  count := make(map[int]int)
  n := len(nums)
  for _, x := range nums {
    count[x]++
    if count[x] > n/2 {
      return x
    }
  }
  return -1
}
func main() {
  nums := []int{3, 2, 3}
  fmt.Println(majorityElement(nums))
  nums = []int{2, 2, 1, 1, 1, 2, 2}
  fmt.Println(majorityElement(nums))
}

代码2： 排序

package main
import (
  "fmt"
  "sort"
)
func majorityElement(nums []int) int {
  sort.Ints(nums)
  return nums[len(nums)/2]
}
func main() {
  nums := []int{3, 2, 3}
  fmt.Println(majorityElement(nums))
  nums = []int{2, 2, 1, 1, 1, 2, 2}
  fmt.Println(majorityElement(nums))
}

代码3：摩尔投票法

维护一个候选元素 candidate 和它出现的次数 count，在遍历数组时，如果当前元素与 candidate 相同，则 count 加 1，否则 count 减 1。如果 count 减为 0，说明前面的元素无法组成多数元素，此时将 candidate 更新为当前元素，并将 count 设为 1。由于多数元素出现的次数大于 ⌊ n/2 ⌋，所以最后 candidate 中存储的一定是多数元素。

package main
import "fmt"
func majorityElement(nums []int) int {
  candidate, count := 0, 0
  for _, x := range nums {
    if count == 0 {
      candidate = x
    }
    if x == candidate {
      count++
    } else {
      count--
    }
  }
  return candidate
}
func main() {
  nums := []int{3, 2, 3}
  fmt.Println(majorityElement(nums))
  nums = []int{2, 2, 1, 1, 1, 2, 2}
  fmt.Println(majorityElement(nums))
}

只有第3种方法满足进阶的复杂度要求。

输出：

170. 两数之和 III Two-sum-iii-data-structure-design

设计一个接受整数流的数据结构，并检查它是否有一对总和为特定值的整数。

实现 TwoSum 类：

TwoSum() 初始化 TwoSum 对象，初始为空数组

void add(int number) 将数字添加到数据结构中。

boolean find(int value) 如果存在任何一对和等于 value 的数字，则返回 true，否则返回 false。

示例：

输入：

["TwoSum", "add", "add", "add", "find", "find"]

[[], [1], [3], [5], [4], [7]]

输出：[null, null, null, null, true, false]

解释：

TwoSum twoSum = new TwoSum();

twoSum.add(1); // [] --> [1]

twoSum.add(3); // [1] --> [1,3]

twoSum.add(5); // [1,3] --> [1,3,5]

twoSum.find(4); // 1 + 3 = 4, 返回 true

twoSum.find(7); // 没有两个整数的和等于 7

约束条件：

-10^5 <= number <= 10^5

-2^31 <= value <= 2^31 - 1

最多调用 10^4 次 add 和 find

代码：

package main
import "fmt"
type TwoSum struct {
  cache map[int]int
}
func Constructor() TwoSum {
  return TwoSum{make(map[int]int)}
}
func (this *TwoSum) add(number int) {
  this.cache[number]++
}
func (this *TwoSum) find(value int) bool {
  for num, count := range this.cache {
    complement := value - num
    if complement == num {
      if count >= 2 {
        return true
      }
    } else if _, ok := this.cache[complement]; ok {
      return true
    }
  }
  return false
}
func main() {
  twoSum := Constructor()
  twoSum.add(1)
  twoSum.add(3)
  twoSum.add(5)
  fmt.Println(twoSum.find(4))
  fmt.Println(twoSum.find(7))
}