leetecode
原文链接： leetecode
4. 寻找两个有序数组的中位数
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 ,请你找出这两个有序数组的中位数.
并且要求算法的时间复杂度为 O(log(m + n))。你可以假设 nums1 和 nums2 不会同时为空。
示例 1: 奇数为中间的数
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2: 偶数为中间两数的平均
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
nums1.extend(nums2)
nums1.sort() # 为什么要造轮子
len1 =len(nums1)
res = (nums1[len1//2]+nums1[(len1+1)//-2])/2.0 # 假设两个数组都不为空,这里就不会报错
return res
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
nums := append(nums1, nums2...)
sort.Ints(nums)
n := len(nums)
return float64(nums[n/2]+nums[(n-1)/2]) / 2
}
[136] 只出现一次的数字 (异或的用法)
- https://leetcode-cn.com/problems/single-number/description/
- 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
func singleNumber(nums []int) int {
// ^ 相同为假，不同为真,相同数字做^异或运算，会得到0。
// 0010 0100
// ^
// 0010 0100
// =
// 0000 0000
var out = 0
for i := 0; i < len(nums); i++ {
out ^= nums[i]
}
return out
}
[169] 求众数 (摩尔投票法)
- https://leetcode-cn.com/problems/majority-element/description/
- 摩尔投票算法是基于这个事实：每次从序列里选择两个不相同的数字删除掉（或称为“抵消”），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个.
// MooreVoting finds the index of most popular element in the list using the
// Moore's Voting algorithm
// The runtime is O(n), space complexity is O(1)
func majorityElement(nums []int) int {
candidate, count := 0, 0
for _, v := range nums {
if count == 0 {
candidate = v
count ++
}else if v != candidate {
count --
} else {
count ++
}
}
return candidate
}