Offer IN 使用案例

面试助手快速跳转：软件工程师 | 硬件工程师 | 产品、运营、商分 | 机械、制造、工程 | 职能岗

笔试助手快速跳转：技术岗 | 非技术岗

面试助手

软件工程师

前端工程师

后端工程师

算法工程师

硬件工程师

IC工程师

嵌入式工程师

产品、运营、商分

产品经理

运营

商分

机械、制造、工程

机械工程师

结构工程师

职能岗

财务

HR

笔试助手

技术岗

非技术岗

小窗模式 - 编程题

问题

一个数据先递增再递减，找出数组不重复的个数。不能使用额外空间，复杂度o(n)

回答

解题思路

核心思路： 我们可以利用数组先递增后递减的特性来解决这个问题。左右各自设置一个指针，分别从数组的头部和尾部开始，向中间移动。由于数组是先递增后递减的，我们可以比较左右两个指针指向的元素的大小，移动较小的一方的指针直到两个指针相遇。在这个过程中，记录遇到的不同的元素数量即可。

解题步骤：

1. 初始化两个指针：left指针在数组头部，right指针在数组尾部；初始化计数器count为0以及两个变量prevLeft和prevRight分别存储左右两个指针上一次访问的值，初始值设为一个数组中不可能出现的值，以便于处理数组中的第一个元素和最后一个元素。
2. 进入一个循环，直到left > right结束循环。在循环内：
   1. 如果arr[left]不等于prevLeft，增加计数器，更新prevLeft。
   2. 如果arr[right]不等于prevRight且left不等于right，则增加计数器，更新prevRight。
   3. 根据arr[left]和arr[right]的值，移动较小一方的指针（如果相等，移动任意一个）。
3. 返回计数器count即为不重复的元素数量。

复杂度分析

• 时间复杂度： $O(n)$，因为每个元素最多被访问两次（一次可能由left指针，一次可能由right指针），所以整体算法的时间复杂度是线性的。
• 空间复杂度： $O(1)$，算法只使用了常数个辅助变量来存储指针和计数等信息。

代码实现

def countUniqueElements(arr):
    if not arr:
        return 0
    n = len(arr)
    left, right = 0, n - 1
    count = 0
    prevLeft, prevRight = float('-inf'), float('-inf') # 初始化为不可能的值
    while left <= right:
        # 处理左指针和右指针指向的元素
        if arr[left] != prevLeft:
            count += 1
            prevLeft = arr[left]
        if arr[right] != prevRight and left != right:
            count += 1
            prevRight = arr[right]
            
        # 移动指针
        if arr[left] < arr[right]:
            left += 1
        else:
            right -= 1
            
    return count
 
# 示例
arr = [1, 2, 3, 4, 5, 5, 4, 3, 2, 1]
print(countUniqueElements(arr)) # 输出不重复的元素个数

在上面的代码中，prevLeft和prevRight确保了即使在边界情况下（例如，数组开始或结束时序列中只有单调递增或单调递减的部分），我们也能正确计算唯一元素的数量。同时，left和right指针的移动策略保证我们遍历了所有元素，而不会遗漏或重复计算任何元素。