• 1

  • 1

  • 收藏

【数据结构与算法】0x1 - 绪论与复杂度分析 | 刷题打卡

1个月前

0x1、一些有的没有的概念

Tips:大学生应试可能需要,面试的知道下就好,不用记~

0x2、如何度量一个算法的优劣

补充:最好、最坏、平均时间复杂度

简单例子:在一个无序数组中,查找是否存在某个值,存在返回下标,不存在返回-1,示例代码如下:

public int indexOf(int[] array, int value) {
    for (int i = 0; i < array.length; i++) {
        if (array[i] == value) return i;
    }
    return -1;
}
复制代码
  • 最好时间复杂度:O(1),查找的值正好是第一个元素;
  • 最坏时间复杂度:O(n),数组中不存在这个值,整个数组都遍历一遍;
  • 平均时间复杂度:O(n),在所有情况下执行次数/所有情况数,计算细则如下:

有n+1种情况(0~n-1位置、不在数组中),然后所有遍历次数累加:1+2+...+n+n,用后者除以前者即可得到平均时间复杂度,推导过程如下:

  1 + 2 + . . + n + n n + 1 = ( ( n + 1 ) × n 2 + n ) ) × 1 n + 1 = n × ( n + 3 ) 2 × 1 n + 1 = n ( n + 3 ) 2 ( n + 1 ) \frac{1+2+..+n+n}{n+1} = ((n + 1)\times \frac{n}{2} + n)) \times \frac{1}{n+1} = \frac{n \times (n+3)}{2} \times \frac{1}{n+1}= \frac{n(n+3)}{2(n+1)}   大O标记法中,可省略掉系数、低阶、常量,简化后时间复杂度即为:O(n)

Tips:大多数情况不需要我们区分最好、最坏、平均情况的时间复杂度,平常说的复杂度都是最坏复杂度

0x3、两个循序渐进的单例子

1、求1+2+...100的和

暴力解法(程序优化的起点):从1开始到100,循环相加得出结果,不难写出下述程序:

public int sum(int n) {
    int sum = 1;
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}
复制代码

单段代码看高频,此处看循环,循环n次,故时间复杂度O(n),而利用高斯求和公式,可将时间复杂度降低为常数阶O(1)

public int gsSum(int n) {
    return (n + 1) * n / 2;
}
复制代码

2、【剑指Offer-03】数组中重复的数字

题目描述

要点分析

就是找出数组里任意一个重复的数字,留心限制:长度为n的数组,数字范围0~n-1

① 暴力解法:两个for循环一把梭。

public int findRepeatNumber(int[] nums) {
    for(int i = 0; i < nums.length; i++) {
        for(int j = i + 1; j < nums.length; j++) {
            if(nums[i] == nums[j]) {
                return nums[i];
            }
        }
    }
    return -1;
}
复制代码

嵌套代码求乘积,两层循环,故暴力解法的时间复杂度为O(n^2),LeetCode上执行代码还好,提交却超时了:

得想办法降低时间复杂度,因为数组无序,未排序的情况下无法使用二分法查找,所以至少得遍历1次,即时间复杂度至少为O(n),用另外一个数据结构来保存遍历结果,当出现重复,返回重复数字。

② Hash表:遍历时判断元素是否在表中,不在保存,在说明元素重复,直接返回。

public int findRepeatNumber(int[] nums) {
    HashSet<Integer> countSet = new HashSet<>();
    for (int num : nums) {
        if (countSet.contains(num)) return num;
        countSet.add(num);
    }
    return -1;
}
复制代码

利用Hash表这种数据结构把时间复杂度变成了O(n),除了用Hash表,还可以用辅助数组实现。

③ 辅助数组:把遍历时获取的值,辅助数组[值]++,如果大于1说明重复了,返回值。

public int findRepeatNumber(int[] nums) {
    int[] countArr = new int[nums.length];
    for (int num : nums) {
        countArr[num]++;
        if (countArr[num] > 1) {
            return num;
        }
    }
    return -1;
}
复制代码

时间复杂度和Hash表一样都是O(n),空间复杂度也为O(n),此处其实还可以再优化下,把自增改为赋值1,然后判断是否等于1:

public int findRepeatNumber(int[] nums) {
    int[] countArr = new int[nums.length];
    for(int pos = 0; pos < nums.length; pos++) {
        if(countArr[nums[pos]] == 1) return nums[pos];
        countArr[nums[pos]] = 1;
    }
    return -1;
}
复制代码

这里还有个坑要注意下:如果 元素值>数组长度,会出现数组越界,比如有个元素1000,然后数组长度为10,这里因为题目做了限制,长度为n的数组,数字范围0~n-1,所以不用担心这个问题。

④ 数组重排:不利用辅助数组,利用索引和值的关系,会改变原数据。

以题目的输入为例,罗列下变化,以便理解规律:

// 原数组
2 3 1 0 2 5 3

// nums[0] == 2,将nums[2]的值与nums[0]的值交换后:
1 3 2 0 2 5 3

// nums[0] == 1,将nums[1]的值与nums[0]的值交换后:
3 1 2 0 2 5 3

// nums[0] == 3,将nums[3]的值与nums[0]的值交换后:
0 1 2 3 2 5 3

// nums[0] == 0,往后走nums[1] == 1,往后走nums[2]=2,往后走nums[3]=3
// nums[4] == 2,而此时nums[2] == 2,说明元素重复,直接返回。
复制代码

弄懂上面的操作,写出代码就很容易了:

public int findRepeatNumber(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        while (nums[i] != i) {
            if (nums[nums[i]] == nums[i]) return nums[i];
            // 元素交换
            int temp = nums[nums[i]];
            nums[nums[i]] = nums[i];
            nums[i] = temp;
        }
    }
    return -1;
}
复制代码

时间复杂度为O(n),只用到一个辅助变量,故空间复杂度为O(1),和辅助数组的解法一样有数组越界的坑~


本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情

免责声明:文章版权归原作者所有,其内容与观点不代表Unitimes立场,亦不构成任何投资意见或建议。

java

1

相关文章推荐

未登录头像

暂无评论