数据结构与算法——数组-阿里云开发者社区

开发者社区> 人工智能> 正文

数据结构与算法——数组

简介: 数组 题型1:如何用递归实现数组求和 方法1: 题型2:如何用一个for循环打印一个二维数组 方法1:array在二维数组中的行号和列号分别为[i/MAXY],[i%MAXY] 题型3:用递归和非递归的方法实现二分查找 题型4:如何在排序数组中,找出给定数字出现的次数 方法1:二分查找...

数组

题型1:如何用递归实现数组求和

方法1:

题型2:如何用一个for循环打印一个二维数组

方法1:array在二维数组中的行号和列号分别为[i/MAXY],[i%MAXY]

题型3:用递归和非递归的方法实现二分查找

题型4:如何在排序数组中,找出给定数字出现的次数

方法1:二分查找,分别找出左边界和右边界,左右边界的差

方法2:顺序查找,统计计数

题型5:如何计算两个有序整型数组的交集

方法1:采用二路归并来遍历两个数组,分别用i、j从头开始遍历两个数组,如果arr[i]<arr[j],i++;如果arr[i]>arr[j],j++;否则将arr[i]存放到交集中,i++,j++;

方法2:顺序遍历两个数组,将数组元素存放到哈希表中,同时统计的数组元素进行计数。如果为2,则为两者的交集元素

方法3:遍历两个数组中任意一个数组,将遍历得到的元素放到哈希表,然后遍历另外一个数组,同时对建立的哈希表进行查询,如果存在,则为交集元素

题型6:如何找到数组中重复次数最多的数

方法1:以空间换时间,可以定义一个数组int count[MAX],并将其数组元素都初始化为0,然后遍历数组,对count[A[i]]++操作,在count中找出最大的数。

方法2:使用map映射表,通过引入map表,其中第一为关键字,第二个为关键字出现的次数,然后判断次数大小。

题型7:如何在O(n)的时间复杂度内找到数组中出现次数超过了一半的数

方法1:hash法,首先创建一个hash_map,其中key为数组元素值,value为此数出现的次数。遍历一遍数组,用hash_map统计每个数出现的次数。

方法2:partition法,由于出现次数最多的元素肯定也会是中位数,所以,每次用patition找到一个数的位置,如果该数刚好为中位数,则就是超过了一半的数。

方法3:每次取出两个不同的数,剩下的数字中重复出现的数字肯定比其他数字多,将规模缩小化。如果每次都删除两个不同的数,那么剩下的数字里,原频度最高的数出现的频率一样超过了50%。

题型8:如何找到数组中唯一的重复元素(数组a[N],1至N-1个数存放在a[N]中,其中某个数重复一次)

方法1:由于题目要求每个元素只访问一次,不用辅助存储空间,可以从原理上入手,采用数学求和法,因为只有一个数字重复一次,而数又是连续的,根据累加原理,对数组的所有项求和,然后减去1至N-1的和,即为所求的重复数。

方法2:采用异或的方法,相同的数为0,不相同的数为1.

方法3:位图法,首先申请一个长度为N-1且均为‘0’组成的字符串,然后从头开始遍历数组a[N],取每个数组元素a[i]的值,将其对应的字符串中的相应位置置为1,如果已经置过1,那么该数就是重复的数。

题型9:如果判断一个数组中的数值是否连续相邻

一个整数数列,元素取值可能是0~65535中的任意一个数,相同元素不会重复出现;0是个例外,可以反复出现。如果最大值和最小值的差距大于0的个数,那么就是不连续的。(如果数组中的元素有重复的,则需要顺序求看是否有重复元素以及间隔)

题型10:如何找出数组中出现奇数次的元素

方法1:使用异或的方法,将所有元素进行异或最后剩下的将是出现奇数次的元素

引申:由n个元素组成的数组,n-2个数出现了偶数此,两个数出现了奇数次(这两个数不相等),如何用O(1)的空间复杂度,找出这两个数?

将所有数异或之后,结果相当于将不相等的两个数a和b异或。x=a^b,求出x中最低位为1,其中肯定a和b中有一个数的该位是为1的,对数组中所有该位为1的数进行异或,所有该位为0的数进行异或。将能分别得到这两个数。

题型11:如何找出数列中符号条件的数对的个数

方法1:蛮力法,求所有可能的数对的和,看其和是否为该数

方法2:先对数组进行排序,然后使用二分查找方法,用两个指示器分别指向第一个和最后一个元素,然后从两端同时向中间遍历,直到两个指针交叉。

方法3:用计数排序,将1~N个数放在一块很大的空间里面,比如1放在1号位,N放在N号位,O(N)的时间复杂度,然后取值。

引申:如果是任意数组而不是有规律的数组,如何求解数组对?即给定一个任意整数数组array[n],寻找数组中和值为SUM的数对。

方法1:蛮力法

方法2:同上面的方法2

方法3:将数组hash到hash表,然后在hash表中查找SUM-m

引申:已知大小分别为m、n的两个无序数组A、B和一个数常数c,求满足A[i]+B[j]=c的所有A[i]和B[j]

方法1:枚举法

方法2:排序+二分查找法

方法3:排序+线性扫描法

方法4:map,将一个数组存放到map中,遍历另一个数组,对于数m,在map中查找SUM-m

题型12:如何寻找数列中缺失的数

给一个由n-1个整数组成的未排序的序列,其元素都是1~n中的不同的整数。如何寻找序列中缺失的整数

可以通过累加求和。首先将该n-1个整数详解,得到sum,然后用(1+n)n/2减去sum,得到的差即为缺失的整数。

题型13:如何判定数组是否存在重复元素(假设数组a有n个元素,元素取值范围是1~n,如何判定数组是否存在重复元素)

方法1:对数组进行排序,然后比较相邻的元素是否相同。时间复杂度O(nlogn)

方法2:使用bitmap方法,定义长度为N/8的char数组,每个bit表示对数字是否出现过。遍历数组,使用bitmap对数字是否出现进行统计。时间复杂度O(n),空间复杂度O(n)

方法3:遍历数组,假设第i个位置的数字是A[i],并且i!=A[i],则将A[i]交换到下标为A[i]的位置,如果下标为A[i]的位置已经有A[i]==A[A[i]],则出现重复了。

题型14:如何重新排序数组使数组左边为奇数,右边为偶数。

方法1:使用快速排序类似的方法,使用两个指针分别指向头和尾,如果不是指向对应的数,则将二者进行交换

题型15:如何把一个整型数组中重复的数字去掉。

方法1:就是遍历数组的每一个元素,将元素与前面的已经遍历过的元素进行逐一比较,如果发现与前面的数组重复,则去掉;如果没有重复,则继续遍历下一个元素。由于每一个元素都要与之前所有元素比较,所以时间复杂度为O(n^2)

方法2:将元素进行排序,然后遍历每一个元素,并用count记录不重复元素的个数,如果当前元素与它前一个元素不相同,执行A[count]=A[i],count++;否则执行下一次循环。

题型16:如何找出一个数组中第二大的数。

方法1:对所有元素进行排序,第二大的数在第二个位置

方法2:用两个变量分别记录第一大和第二大的数,对于最大值初始值为首元素,第二大的数初始化为最小的负数。每次用当前元素与最大值比较,如果大于最大值,则将其赋给最大值,将原最大值赋给第二大值,否则如果小于最大值,则与第二大值进行比较。

题型17:如何将数组的后面m个数移动为前面m个数

方法1:

将前m个元素的顺序颠倒;

将后面n-m个元素的顺序颠倒

将n个元素的顺序全部颠倒

题型18:如何计算出序列的前n项数据

正整数序列Q中的每个元素都至少能被正整数a和b中的一个整除,现给定a和b,如何计算出Q中的前几项?例如,当a=3,b=5,N=6时,序列3,5,6,9,10,12.可以和归并联系起来,给定两个数组A、B,数组A 存放:3*1,3*2,3*3...数组B存放5*1,5*2,5*3...有两个指针i、j分别指向A、B的第一个元素,取min(A[i],B[j])并移动较小值的指针,然后继续比较。

引申:丑数,是只能包含因子2 3 5的数。

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章