代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素
小收获
数组是存放在连续内存空间上的相同类型数据的集合
测试一下go
func main() {
fmt.Printf("Size of int: %d bytes\n", unsafe.Sizeof(int(0)))
fmt.Printf("Size of int8: %d bytes\n", unsafe.Sizeof(int8(0)))
fmt.Printf("Size of int16: %d bytes\n", unsafe.Sizeof(int16(0)))
fmt.Printf("Size of int32: %d bytes\n", unsafe.Sizeof(int32(0)))
fmt.Printf("Size of int64: %d bytes\n", unsafe.Sizeof(int64(0)))
fmt.Printf("Size of uint: %d bytes\n", unsafe.Sizeof(uint(0)))
fmt.Printf("Size of uint8: %d bytes\n", unsafe.Sizeof(uint8(0)))
fmt.Printf("Size of uint16: %d bytes\n", unsafe.Sizeof(uint16(0)))
fmt.Printf("Size of uint32: %d bytes\n", unsafe.Sizeof(uint32(0)))
fmt.Printf("Size of uint64: %d bytes\n", unsafe.Sizeof(uint64(0)))
fmt.Println("========================================================")
var testlist = []int{1, 2, 3, 4, 5}
for idx, _ := range testlist { // for range 的变量是同一个内存地址
fmt.Printf("内存地址:%p\n", &testlist[idx])
}
}
//Size of int: 8 bytes
//Size of int8: 1 bytes
//Size of int16: 2 bytes
//Size of int32: 4 bytes
//Size of int64: 8 bytes
//Size of uint: 8 bytes
//Size of uint8: 1 bytes
//Size of uint16: 2 bytes
//Size of uint32: 4 bytes
//Size of uint64: 8 bytes
//========================================================
//内存地址:0xc0000120d0
//内存地址:0xc0000120d8
//内存地址:0xc0000120e0
//内存地址:0xc0000120e8
//内存地址:0xc0000120f0
// 多维数组同样连续
func main() {
var testlist = [][]int{{1, 2}, {3, 4}}
for y, li := range testlist {
for x, _ := range li {
fmt.Printf("[%d][%d]%p\n", x, y, &testlist[y][x])
}
}
}
// [0][0]0xc0000120c0
// [1][0]0xc0000120c8
// [0][1]0xc0000120d0
// [1][1]0xc0000120d8
704 二分查找
- 思路
二分,即为每次将列表的长度缩短一半,所以需要保存中间索引,并不断更新直至找到结果
func search(nums []int, target int) int {
left, right := 0, len(nums) - 1
for left <= right { // 边界条件,可以思考极端情况,比如2个值【0,1】, 此时如果不取等于,那么最多只能查找一次 !!!! 看了视频才知道,通过区间是否合法判断更简单,淦,我这个是左闭右闭,所以应该加上等于条件
mid := (left + right) / 2
if nums[mid] == target{
return mid
}
if nums[mid] < target {
left = mid + 1
}
if nums[mid] > target {
right = mid - 1
}
}
return -1
}
// 此实现方式 时间复杂度:log2n(每次长度缩减一半) 空间:1 (只启用了有限的变量保存)
// 递归思路,大事化小,将长列表逐渐二分缩短直至为长度为1的列表,此时可以直接判断是否等于target
// 个人想法,做简单递归前可以尝试循环解决,然后再转为递归可能更好书写
func search(nums []int, target int) int {
return recursion(nums, 0, len(nums)-1, target)
}
func recursion(nums []int, low, high, target int)(result int ){
if low > high { // 参考简单二分的循环条件相反递归的一种极端结束条件
return -1
}
mid := (low + high) / 2
if nums[mid] == target {
return mid // 递归终止条件
}
// 通过保存变量方式可以更直观理解,当让也可以通过直接return 递归函数更简洁
if nums[mid] < target{
result = recursion(nums, mid+1, high, target) // 仅仅相当于将low = mid+ 1的循环体放入递归中处理
}else {
result = recursion(nums, low, mid-1, target) // 同理
}
return result
}
时间 logn 空间logn
27 删除列表元素
// 题目真难读懂,简单说就是列表移除某个值元素,然后重新排列,保证剩余元素再列表前几位就行,顺序不论
func removeElement(nums []int, val int) int {
// 思路: 最简单遍历
for i := 0; i < len(nums); {
if nums[i] == val {
nums = append(nums[:i], nums[i+1:]...) // 本质上删除nums[i]
} else {
i++
}
}
return len(nums)
}
时间 遍历n*append移动n次 = n^2 空间 每次append都可能分配新数组所以 n
func removeElement(nums []int, val int) int {
// 思路:快慢指针,快指针如果不等于val就赋值给慢指针,如果等于那么就++
slow := 0
for fast := 0; fast < len(nums); fast++ {
if nums[fast] != val {
nums[slow] = nums[fast]
slow++
}
}
return slow
}
热门相关:鬼喊抓鬼 九星毒奶 甜蜜婚令:首长的影后娇妻 福晋有喜:四爷,宠上天! 末日乐园