数据结构和算法学习记录——时间复杂度、空间复杂度相关练习题

简介: 数据结构和算法学习记录——时间复杂度、空间复杂度相关练习题

一、消失的数字

题目描述

数组nums包含从0到n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗?

示例 1

输入:[3,0,1]

输出:2

示例 2

输入:[9,6,4,2,3,5,7,0,1]

输出:8

解法一

对0到n的所有整数进行求和,再对数组的所有数进行求和。相减得到的差值即为数组中消失的一个数字。

int missingNumber(int* nums, int numsSize)
{
    int i,S1 = 0,S2 = 0;
    //0到n的求和,也可以用等差求和公式
    for(i = 0;i <= numsSize;i++)
        S1 += i;
 
    //数组所有数的求和
    for(i = 0;i < numsSize;i++)
        S2 += nums[i];
    return (S1 - S2);
}

解法二

解法二是利用异或的特性。异或的计算规则按二进制位对比,相同的则为0,不同的则为1.

存在法则:有一个变量a一、a ^ a = 0 ,即一个数异或它本身,得到的结果为0。二、0 ^ a = a ,即一个数异或0,得到的结果为它本身。

这个法则是无关顺序的,例如:

int main()
{
    int arr1[7] = { 1,2,3,1,2,3,4 };
    int arr2[7] = { 3,2,1,3,2,1,6};
    int x = 0,i = 0;
    for (i = 0; i < 7; i++)
        x ^= arr1[i];
    printf("%d\n",x);
    x = 0;
    for (i = 0; i < 7; i++)
        x ^= arr2[i];
    printf("%d\n", x);
    return 0;
}

arr1中有相同的1,2,3;arr2中也有相同的3,2,1。他们全部异或在一起之后得到的结果会等于0,最终0异或4得到4,,异或6得到6。

所以可以根据这个特性来找出消失的数字,先创建变量x = 0,再让x逐一异或0到n的数字,以及数组。最终相同的数字被消去,只剩下孤单的数字。

int missingNumber(int* nums, int numsSize)
{
    int x = 0,i;
    for(i = 0;i <= numsSize;i++)
    {
        x ^= i;
    }
    for(i = 0;i < numsSize;i++)
    {
        x ^= nums[i];
    }
    return x;
}

二、轮转数组

题目描述

给定一个整数数组 nums ,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。

示例1

输入: nums = [1,2,3,4,5,6,7], k = 3

输出: [5,6,7,1,2,3,4]

解释:

向右轮转 1 步: [7,1,2,3,4,5,6]

向右轮转 2 步: [6,7,1,2,3,4,5]

向右轮转 3 步: [5,6,7,1,2,3,4]

示例2

输入:nums = [-1,-100,3,99], k = 2

输出:[3,99,-1,-100]

解释:

向右轮转 1 步: [99,-1,-100,3]

向右轮转 2 步: [3,99,-1,-100]

解法

解这道题我们用到三步翻转,拿示例1来看。

void Reverse(int * arr,int left ,int right)
{
    while(left < right)
    {
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
        left++;
        right--;
    }
}
void rotate(int* nums, int numsSize, int k)
{
    //当k大于或等于数组大小时,则不需要进行轮转
    if(k >= numsSize)
        k %= numsSize;
 
    //翻转一次
    Reverse(nums,0,numsSize-k-1);
 
    //翻转两次
    Reverse(nums,numsSize-k,numsSize-1);
 
    //翻转三次
    Reverse(nums,0,numsSize-1);
}
目录
相关文章
|
19天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
19天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
19天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
19天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
19天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
19天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
19天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
25天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
10天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。
|
11天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。