2485. 找出中枢整数 Find the Pivot Integer

问题描述

这个问题的解法就比较多了.

前缀和 Prefix Sum

根据问题中的描述, 可以直接想到的方法就是前缀和.

处理步骤如下:

1. 构造 [1..=n] 的前缀和数组
2. 遍历前缀和数组, 如果左侧部分等于右侧部分, 就返回, prefix * 2 == total_sum + i as i32
3. 否则没有找到, 就返回 -1

代码实现如下:

#![allow(unused)]
fn main() {
// Prefix Sum
pub fn pivot_integer1(n: i32) -> i32 {
    let len = (n + 1) as usize;

    // 构造前缀和数组
    let mut prefix_sum = vec![0_i32; len];
    prefix_sum[0] = 0;
    prefix_sum[1] = 1;
    for i in 2..len {
        prefix_sum[i] = prefix_sum[i - 1] + i as i32;
    }

    let total_sum = prefix_sum[len - 1];

    // 遍历前缀和数组
    for (i, prefix) in prefix_sum.into_iter().enumerate() {
        // 满足左侧之和等于右侧之后
        if prefix * 2 == total_sum + i as i32 {
            return i as i32;
        }
    }

    -1
}
}

该算法的时间复杂度是 O(n), 空间复杂度是 O(n).

双指针法

步骤如下:

1. 构造两个指针, 分别代表左侧之和与右侧之和
   1. 左侧之和初始化为0
   2. 右侧之和被初始化为 n * (n + 1) /2
2. 遍历 1..=n, 然后判断左侧之和与右侧之和的关系
   1. 如果 left_sum + i == right_sum, 说明找到了该位置, 直接返回
   2. 否则更新左侧之和与右侧之和
   3. 如果 left_sum > right_sum, 说明没有找到合适的位置, 直接返回 -1

该算法的实现如下:

#![allow(unused)]
fn main() {
// Two pointers
pub fn pivot_integer2(n: i32) -> i32 {
    let mut left_sum = 0;
    let mut right_sum = n * (n + 1) / 2;

    // 注意遍历的范围, 是 [1..=n]
    for i in 1..=n {
        if left_sum + i == right_sum {
            return i;
        }
        left_sum += i;
        right_sum -= i;
        if left_sum > right_sum {
            break;
        }
}

该算法的时间复杂度是 O(n), 空间复杂度是 O(1).

平方根法

这个方法的原理还不太清楚, 先计录一下.

#![allow(unused)]
fn main() {
// Sqrt
pub fn pivot_integer3(n: i32) -> i32 {
    let sum = n * (n + 1) / 2;
    let sqrt = (sum as f64).sqrt() as i32;
    if sqrt * sqrt == sum {
        sqrt
    } else {
        -1
    }
}
}

该算法的时间复杂度是 O(1), 空间复杂度是 O(1).