（2）数组相关算法题⽬
数组是最简单的数据结构，占据连续内存并且按顺序存储。
以下是与数组有关的算法题⽬。
（1）查询数组中重复数字
算法思路：（1）利⽤hash表，没有便放进去，有就返回（Java中HashMap存数字都是对象，判断数字是否唯⼀变为对象是否唯⼀，-128-127好说，其他不好说）。（2）借助基数排序思想，创建⼀个辅助数组（空间可能会很⼤）（3）i位置上j和j位置上元素互换，若j等于j位置上元素，说明重复（万⼀j的⼤⼩超出了矩数组⼤⼩则JJ）。（4）先排序，然后前后指针来实现，若A[i]==A[j] j++；若A[i]!=A[j] i = j;j++;
（2）⼆维数组的查
算法思路：⾏、列有序，从⼩到⼤，则从右上⾓开始逼近，缩⼩搜索范围。
（3）把数组中的元素循环右移k位如12345678右移两位78123456
算法思路：3次翻转。把123456翻转65432178；把78翻转65432187；整体翻转78123456。
（4）字符数组中所有元素的排列
算法思路：利⽤递归，第⼀个字符⼀共有n种选择，剩下的变成⼀个n-1规模的递归问题。⽽第⼀个字符的n种选择，都是字符串⾥⾯的。因此可以使⽤第⼀个字符与剩下的位置上进⾏交换，得到n种情况，然后递归处理n-1的规模，只是处理完之后需要在换回来，变成原来字符的样⼦。
（5）字符数组中所有元素的组合
算法思路：(1)通过⼆进制数字⽤01表⽰某个元素是否存在来实现，组合是没有顺序要求的（2）假设我们想在长度为n的字符串中求m 个字符的组合。我们先从头扫描字符串的第⼀个字符。针对第⼀个字符，我们有两种选择：⼀是把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选取m-1个字符；⼆是不把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选择m个字符。这两种选择都很容易⽤递归实现。
（6）判断数组中的值是否连续
算法思路：数组中的0可以代替任何元素，如果没有0，则说明最⼤减去最⼩为数组⼤⼩；如果有0，则⼩于数组⼤⼩。例如：8 7 6 0 5。
（7）寻最⼩k个数
算法思路：⽅法⼀：先对这个序列从⼩到⼤排序，然后输出前⾯的最⼩的k个数；⽅法⼆：是维护容量为k的最⼤堆；⽅法三：快排思想。Partation，线性时间复杂度算法。
（8）和为定值的两个数
算法思路：1、⼆分（若⽆序，先排序后⼆分），时间复杂度总为O(N log N)，空间复杂度为O（1）；2、扫描⼀遍X-S[i] 映射到⼀个数组或构造hash表，时间复杂度为O(N)，空间复杂度为O(N)；3、两个指针两端扫描（若⽆序，先排序后扫描），时间复杂度最后为：有序
数学二进制的算法O(N)，⽆序O(Nlog N + N)=O(N log N)，空间复杂度都为O(1)。
（9）和为定值的多个数
算法思路：如果取第n个数，那么问题就转化为“取前n-1个数使得它们的和为sum-n”，对应的代码语句就是sumOfkNumber(sum -n, n - 1)；如果不取第n个数，那么问题就转化为“取前n-1个数使得他们的和为sum”，对应的代码语句为sumOfkNumber(sum, n - 1)。通过递归解法求出。
（10）奇偶排序
输⼊⼀个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求时间复杂度为
O(n)。
⽅法1: 借鉴partition的实现⼀，我们可以考虑维护两个指针，⼀个指针指向数组的第⼀个数字，我们称之为头指针，向右移动；⼀个指针指向最后⼀个数字，称之为尾指针，向左移动。这样，两个指针分别从数组的头部和尾部向数组的中间移动，如果第⼀个指针指向的数字是偶数⽽第⼆个指针指向的数字是奇数，我们就交换这两个数字。
⽅法2：我们也可以维护两个指针i和j，⼀个指针指向数组的第⼀个数的前⼀个位置，我们称之为后指针i，向右移动；⼀个指针指向数组第⼀个数，称之为前指针j，也向右移动，且前指针j先向右移动。如果前指针j指向的数字是奇数，则令i指针向右移动⼀位，然后交换i和j指针所各⾃指向的数字
（11）荷兰国旗
现有n个红⽩蓝三种不同颜⾊的⼩球，乱序排列在⼀起，请通过两两交换任意两个球，使得从左⾄右，依次是⼀些红球、⼀些⽩球、⼀些蓝球。
荷兰国旗问题
算法思路：这个问题类似快排中partition过程，只是需要⽤到三个指针：⼀个前指针begin，⼀个中指针current，⼀个后指针
end，current指针遍历整个数组序列，当
current指针所指元素为0时，与begin指针所指的元素交换，⽽后current++，begin++ ；
current指针所指元素为1时，不做任何交换（即球不动），⽽后current++ ；
current指针所指元素为2时，与end指针所指的元素交换，⽽后，current指针不动，end--
（12）完美洗牌算法
有个长度为2n的数组{a1,a2,a3,...,an,b1,b2,b3,...,bn}，希望排序后{a1,b1,a2,b2,....,an,bn}，请考虑有⽆时间复杂度o(n)，空间复杂度
0(1)的解法。
算法思路：⽅法1：蛮⼒B中的数步步前移；或者从中间开始两两交换；⽅法2: 前n个元素中，第i个元
素去了第（2 * i）的位置。后n个元素，第i个元素去了第 (2 (i - n) ) - 1 = 2 i - (2 n + 1) = (2 i) % (2 * n + 1) 个位置。
（13）不使⽤除法进⾏数组运算
常见的算法⾯试题：两个数组a[N]，b[N]，其中A[N]的各个元素值已知，现给b[i]赋值，b[i]
= a[0]a[1]a[2]...*a[N-1]/a[i]；要求解b[i]，但是：
1.不准⽤除法运算
2.除了循环计数值，a[N],b[N]外，不准再⽤其他任何变量（包括局部变量，全局变量等）
3.满⾜时间复杂度O(n)，空间复杂度O(1)。
算法思路：题⽬要求b[i] = a[0]a[1]a[2]...a[N-1]/a[i] ，相当于求：a[0]a[1]a[2]a[3]...a[i-1]a[i+1]..a[N-1]，等价于除掉当前元素a[i]，其他所有元素(a[i]左边部分，和a[i]右边部分)的积。
（14）数组中唯⼀重复元素
1-1000放在含有1001个元素的数组中，只有唯⼀的⼀个元素值重复，其它均只出现⼀次。每个数组元
素只能访问⼀次，设计⼀个算法，将它出来；不⽤辅助存储空间，能否设计⼀个算法实现？
算法思路：做加法求和。
（15）出唯⼀出现的数
⼀个数组⾥，数都是两两出现的，但是有三个数是唯⼀出现的，出这三个数。
算法思路：相同数做异或运算结果为0，多次异或运算即可求出。
（16）出反序的个数
给定⼀整型数组，若数组中某个下标值⼤的元素值⼩于某个下标值⽐它⼩的元素值，称这是⼀个反序。即：数组a[]; 对于i < j 且 a[i] > a[j]，则称这是⼀个反序。给定⼀个数组，要求写⼀个函数，计算出这个数组⾥所有反序的个数。
算法思想：归并算法的思路。归并中需要调整的次数即反序的个数。
（17）两个数组元素求和，最⼩k个数
有两个序列A和B,A=(a1,a2,...,ak),B=(b1,b2,...,bk),A和B都按升序排列，对于1<=i,j<=k，求k个最⼩的
（ai+bj），要求算法尽量⾼效。
算法思路：可借助最⼩堆来解决，由于a1+b1肯定是最⼩的和，⾸先把a1+b1的结果放⼤最⼩堆⾥，此时堆中只有⼀个元素，⾃然满⾜最⼩堆条件，然后开始出堆的操作，从堆⾥⾯取出根节点（也就是最⼩的值），假如此时堆顶元素为ai+bi，则需要像最⼩堆中压⼊a(i+1)+bj的和与
ai+b(j+1)的和，当然，要保证下标不越界，如果下标越界了则忽略，另外要保证已经压⼊过堆中的组合（即使已经从堆中被取出了的）不再被压⼊堆中。不断地进⾏出堆、⼊堆的操作，重复k次，就得到了k个最⼩的组合值。
（18）螺旋矩阵
螺旋状打印矩阵
（19）⼀个整数数组，长度为n，将其分为m份，使各份的和相等，求m的最⼤值。
⽐如{3，2，4，3，6} 可以分成
{3，2，4，3，6} m=1;
{3,6}{2,4,3} m=2
{3,3}{2,4}{6} m=3
所以m的最⼤值为3。
算法思路：从1-N分别划分，和为sum/N的数；
(20)输⼊⼀个正数n，输出所有和为n连续正数序列。
例如输⼊15，由于1+2+3+4+5=4+5+6=7+8=15，所以输出3个连续序列1-5、4-6和7-8。
算法思路：和为定值的N个数的多个K值的版本，且数字顺序要⼀致。若为奇数个，则中间数字为Sum/N；若为偶数个，则sum/n必定余1；通过这种⽅式，可以求出中间数字。
（21）出数组中两个只出现⼀次的数字
题⽬：⼀个整型数组⾥除了两个数字之外，其他的数字都出现了两次。请写程序出这两个只出现⼀次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
算法思路：异或操作。
（22）把数组排成最⼩的数
输⼊⼀个正整数数组，将它们连接起来排成⼀个数，输出能排出的所有数字中最⼩的⼀个。例如输⼊数组{32,321}，则输出这两个能排成的最⼩数字32132。
算法思路：字典序排序，从前往后合并，如A,B⽐较AB与BA的⼤⼩，选最⼩的，然后逐步缩⼩数组长度。
（23）旋转数组的最⼩元素
把⼀个数组最开始的若⼲个元素搬到数组的末尾，我们称之为数组的旋转。输⼊⼀个排好序的数组的⼀个旋转，输出旋转数组的最⼩元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的⼀个旋转，该数组的最⼩值为1。
算法思路：从头到尾遍历数组⼀次，就能出最⼩的元素，时间复杂度显然是O(N)。但这个思路没有利⽤输⼊数组的特性。可以2分查，⽐较到的元素与⾸位和末尾的元素，判断当前元素在哪个递增序列上。
（24）请把⼀个整形数组中重复的数字去掉
例如：1, 2, 0, 2, -1, 999, 3, 999, 88  ；处理后应该是：1, 2， 0， -1， 999， 3，88
算法思路：位图，hashtable.
（25）⼀个数组[1,2,3,4,6,8,9,4,8,11,18,19,100] 前半部分是是⼀个递增数组，后⾯⼀个还是递增数组，但整个数组不是递增数组，那么怎么最快的出其中⼀个数？
算法思路：⽅法⼀：⾸先对前⼀半递增直接查，到即退出，后⼀半⼆分查；⽅法⼆：到零界点。分两个部分⼆分查。临界点可2
分查，⽐较左右来判断。
（26）数组al[0,mid-1] 和al[mid,num-1]，都分别有序。将其merge成有序数组al[0,num-1]，要求空间复杂度O(1)。
算法思路：从中间开始两两互换，互换范围从2-4-6依次扩⼤。
（27）⼀个数组的值先从⼩到⼤递增后从⼤到⼩递减，出最⼤的值
算法思路：⼆分查，到后和左右⽐较
（28）两个⽆序数组分别叫A和B，长度分别是m和n，求中位数，要求时间复杂度O(log（m+n）)，空间复杂度O(1)
算法思路：⾸先先排序，分别求A和B的中位数，然后⽐较之，根据⽐较选择不同的数组区域继续进⾏筛选。假设两个数组
为:Orda_1,Orda_2。先对⽐这个数组的中间数的⼤⼩，假设Orda_1的中间数为a_1,Orda_2的中间数为a_2，如果a_1 >= a_2，那么两个数组的中间数肯定在Orda_1数组前半段和Orda_2数组后半段中，接着再把Orda_1前半段和Orda_2后半段当做新的两个有序数组，重复前⾯的步骤，直⾄递归结束。
（29）约瑟夫环
n个数字（0,1,…,n-1）形成⼀个圆圈，从数字0开始，每次从这个圆圈中删除第m个数字（第⼀个为当前数字本⾝，第⼆个为当前数字的下⼀个数字）。当⼀个数字删除后，从被删除数字的下⼀个继续删除第m个数字。求出在这个圆圈中剩下的最后⼀个数字。
算法思路：每杀掉⼀个⼈，下⼀个⼈成为头，相当于把数组向前移动M位。若已知N-1个⼈时，胜利者的下标位置位f(N−1,M)，则N个⼈的时候，就是往后移动M为，(因为有可能数组越界，超过的部分会被接到头上，所以还要模N)，即f(N,M)=(f(N−1,M)+M)%n
递推公式：
f(N,M)=(f(N−1,M)+M)%N
f(N,M)表⽰，N个⼈报数，每报到M时杀掉那个⼈，最终胜利者的编号
f(N−1,M)表⽰，N-1个⼈报数，每报到M时杀掉那个⼈，最终胜利者的编号
(30)统计在从1到n的正数中1出现的次数
例如输⼊12，从1到12这些整数中包含1 的数字有1，10，11和12，1⼀共出现了5次。
算法思路：设定整数点（如1、10、100等等）作为位置点i（对应n的个位、⼗位、百位等等），分别对每个数位上有多少包含1的点进⾏分析。
根据设定的整数位置，对n进⾏分割，分为两部分，⾼位n/i，低位n%i
当i表⽰百位，且百位对应的数>=2，如n=31456,i=100，则a=314,b=56，此时百位为1的次数有a/10+1=32（最⾼两位0~31），每⼀次都包含100个连续的点，即共有(a/10+1)*100个点的百位为1
当i表⽰百位，且百位对应的数为1，如n=31156,i=100，则a=311,b=56，此时百位对应的就是1，则共有a/10(最⾼两位0-30)次是包含100个连续点，当最⾼两位为31（即a=311），本次只对应局部点00~56，共b+1次，所有点加起来共有（a/10*100）+(b+1)，这些点百位对应为1
当i表⽰百位，且百位对应的数为0，如n=31056,i=100，则a=310,b=56，此时百位为1的次数有a/10=31（最⾼两位0~30）
综合以上三种情况，当百位对应0或>=2时，有(a+8)/10次包含所有100个点，还有当百位为1(a%10==1)，需要增加局部点b+1
之所以补8，是因为当百位为0，则a/10==(a+8)/10，当百位>=2，补8会产⽣进位位，效果等同于(a/10+1)
（31）数量超过⼀半的元素

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。