数组

题型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的数。