代码随想录算法训练营第一天 | 704、27、977

算法
, , ,

704. 二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func search(nums []int, target int) int {
    left := 0
    right := len(nums) - 1

    for left <= right {
        mid := left + (right-left)/2 // 防止整数溢出
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return -1
}

27. 移除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
func removeElement(nums []int, val int) int {
    i := 0 // 慢指针，记录有效元素的位置
    // 快指针 j 遍历所有元素
    for j := 0; j < len(nums); j++ {
        if nums[j] != val {
            // 当遇到不等于 val 的元素时，将其移动到有效位置
            nums[i] = nums[j]
            i++
        }
    }
    return i
}

977. 有序数组的平方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func sortedSquares(nums []int) []int {
    n := len(nums)
    result := make([]int, n)
    left, right := 0, n-1
    index := n - 1 // 从后往前填充

    for left <= right {
        leftSquare := nums[left] * nums[left]
        rightSquare := nums[right] * nums[right]

        // 比较左右平方，较大者存入结果数组末尾
        if leftSquare > rightSquare {
            result[index] = leftSquare
            left++
        } else {
            result[index] = rightSquare
            right--
        }
        index--
    }
    return result
}