找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

优化算法的常用方法,你不会不知道吧?

admin 2020-7-4 13:36 134人围观 C++相关

今jin为大家讲解 LeetCode 第 307 题,是一道简单难度的题目。

每日一笑


餐馆里一个厨师帮工姓蔡,其他人都习惯喊他小蔡,一天有几个客人来吃饭,还没有点菜就听他们喊:“老板,先上小菜。”结果老板就摇着头看着小蔡战战兢兢地走到这个客人的包间里。


题目描述


给定一个整数数组  nums,求出数组从索引 i 到 j  (i ≤ j) 范围内元素的总和,包含 i,  j 两点。

示例:

给定 nums = [-2, 0, 3, -5, 2, -1],求和函数为 sumRange()

sumRange(0, 2) -> 1sumRange(2, 5) -> -1sumRange(0, 5) -> -3说明:

你可以假设数组不可变。会多次调用 sumRange 方法。

来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/range-sum-query-immutable著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

方法一:暴力法


直接使用for循环将索引 i 到 j 之间的每个元素相加。不解释了,简单粗暴。
// Go
type NumArray struct {
 data []int
}

func Constructor(nums []int) NumArray {
 return NumArray{nums}
}

func (this *NumArray) SumRange(i int, j int) int {
 sum := 0
 for k:= i; k <=j; k++ {
  sum += this.data[k]
 }
 return sum
}
// Java
private int[] data;

public NumArray(int[] nums) {
    data = nums;
}

public int sumRange(int i, int j) {
    int sum = 0;
    for (int k = i; k <= j; k++) {
        sum += data[k];
    }
    return sum;
}

暴力法的最大缺点就是耗时,像这里的 sumRange 方法中有一层for循环,时间复杂度为 O(n),题意又说会多次调用 sumRange 方法,所以调用 k 次的话,时间复杂度则为 O(kn) 。

这里的空间复杂度为 O(1),请注意,data 是对 nums 的引用,不是它的副本。

我们在想想能不能优化一下呢~

方法二:缓存


我们可以提前计算出前 i 个数的和,即 a[i] 等于区间 [1,i] 的和,消耗时间为 O(n)

区间 [i,j] 的和求公式为:SumRange(i,j) = sum[j] - sum[i-1],每次查询消耗时间为 O(1),k 次查询时间复杂度为 O(k)

总的来说,时间复杂度为 O(n+k)

当然,这里用了数组来存储和的结果,自然多消耗了空间。这里空间复杂度为 O(n)。一般而言,很多优化都是以空间换时间。

代码实现

// go
type NumArray struct {
 sum []int // 存储[0,i]的和
}

func Constructor(nums []int) NumArray {
 a := NumArray{}
 a.sum = append(a.sum, 0) // 初始化 sum 切片,sum[0]=0
  // 遍历求sum[i]
 for i := 1; i <= len(nums); i++ {
  a.sum = append(a.sum, a.sum[i-1]+nums[i-1])
 }
 return a
}

func (this *NumArray) SumRange(i int, j int) int {
 return this.sum[j+1] - this.sum[i]
}
// java
class NumArray {

private int[] sum;

    public NumArray(int[] nums) {
        sum = new int[nums.length + 1];
        for (int i = 1; i <= nums.length; i++) {
            sum[i] = sum[i-1] + nums[i-1];
        }
    }

    public int sumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
}

郑重声明:

所展示代码已通过 LeetCode 运行通过,请放心食用~


推荐阅读



喜欢本文的朋友,欢迎关注“Go语言中文网”:



Go语言中文网启用微信学习交流群,欢迎加微信:274768166,投稿亦欢迎


----------------------------------------------------------------------------------------------------------------------
我们尊重原创,也注重分享,文章来源于微信公众号:Go语言中文网,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
----------------------------------------------------------------------------------------------------------------------

鲜花

握手

雷人

路过

鸡蛋

yafeilinux和他的朋友们微信公众号二维码

微信公众号

专注于Qt嵌入式Linux开发等。扫一扫立即关注。

Qt开源社区官方QQ群二维码

QQ交流群

欢迎加入QQ群大家庭,一起讨论学习!

我有话说......