2021-05-21：给定一个数组arr，先递减然后递增，返回arr中有

原创

福大大架构师每日一题

修改于 2021-05-22 09:20:17

5540

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2021-05-21：给定一个数组arr，先递减然后递增，返回arr中有多少个绝对值不同的数字？

福大大答案2021-05-21：

双指针。左指针最左，符合条件时右移；右指针最右，符合条件时左移。左指针和右指针，谁大谁移动；同样大，都移动。时间复杂度O(N)，额外空间复杂度O(1)。

代码用golang编写。代码如下：

package main

import (
    "fmt"
)

func main() {
    arr := []int{-2, -2, -3, -4, -3, -3, -2, -2, 3, 4}
    if true {
        ret := diff1(arr)
        fmt.Println(ret)
    }
    if true {
        ret := diff2(arr)
        fmt.Println(ret)
    }
}

func diff1(arr []int) int {
    set := make(map[int]struct{})
    for _, v := range arr {
        set[v] = struct{}{}
    }
    return len(set)
}

// 时间复杂度O(N)，额外空间复杂度O(1)
func diff2(arr []int) int {
    N := len(arr)
    L := 0
    R := N - 1
    count := 0
    leftVal := 0
    rightVal := 0
    for L <= R {
        count++
        leftVal = arr[L]
        rightVal = arr[R]
        if leftVal < rightVal {
            for R >= 0 && arr[R] == rightVal {
                R--
            }
        } else if leftVal > rightVal {
            for L < N && arr[L] == leftVal {
                L++
            }
        } else {
            for L < N && arr[L] == leftVal {
                L++
            }
            for R >= 0 && arr[R] == rightVal {
                R--
            }
        }
    }
    return count
}