下载掌阅APP，畅读海量书库
立即打开
【算法题】
给定一个整型数组，找出一个序列中乘积最大的连续子序列。
例如，数组[2,-5,2,-4]输出80，因为数组[2,-5,2,-4]的最大乘积子序列为[2,-5,2,-4]。
例如，数组[-2,0,-1]输出0，而不是2，因为数组[-2,-1]不是连续子序列。
本题使用两个变量分别记录计算过程中的正数的最大值和负数的最小值。因为数组中的数字可能有正数和负数，所以在计算中需要不断调整这两个数。上述算法题的解法如下：
创建测试类用于验证乘积最大连续子序列的功能，测试类如下：
执行测试代码，执行结果如下：
数组{2, -5, 2, -4}乘积最大连续子序列=80
数组{-2, 0, -1}乘积最大连续子序列=0
【算法题】
给定一个大小为n的数组，找到其中的众数。众数是指在数组中出现次数大于等于n/2的元素。
例如，数组[3,2,3]的众数是3，因为数组长度为3，元素3出现的次数为2次。
例如，数组[2,2,1,1,1,2,2]的众数是2，因为数组长度为7，元素2出现的次数为4次。
可以假设数组是非空的，并且给定的数组总是存在众数。
本题可以使用摩尔投票算法求解。摩尔投票算法是一种在线性时间和空间复杂度的情况下，在一个元素序列中查找包含最多的元素的算法。
摩尔投票算法在局部变量中定义一个序列元素m和一个计数器i，初始情况下计数器为0。依次遍历序列中的每个元素。当遍历到元素x的时候，如果计数器为0，那么将x赋值给m，然后将计数器i设置为1，如果计数器不为0，那么比较序列元素m和x，如果相等，那么计数器i加1，如果不等，那么计数器i减1。序列遍历结束后，最后存储的序列元素m就是这个序列的众数。
摩尔投票算法的局限性是序列中必须有且仅有一个出现次数最多的元素，否则摩尔投票算法将不能检测到正确的结果。
上述算法题的解法如下：
创建测试类用于验证求众数算法的功能，测试类如下：
执行测试代码，执行结果如下：
数组{3, 2, 3}的众数是3
数组{2,2,1,1,1,2,2}的众数是2
【算法题】
给定一个数组，将数组中的元素向右移动k个位置，其中k是非负数。
例如，数组为[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]
上述算法题的解法如下：
创建测试类用于验证旋转数组算法的功能，测试类如下：
执行测试代码，执行结果如下：
{1, 2, 3, 4, 5, 6, 7}旋转3个位置后的结果：
{5, 6, 7, 1, 2, 3, 4}
----------------分割线----------------
{-1, -100, 3, 99}旋转2个位置后的结果：
{3, 99, -1, -100}
【算法题】
给定一个数组array，编写一个函数将数组中所有0移动到数组的末尾，同时保持非零元素的相对顺序。
例如，数组[0,1,0,3,12]返回[1,3,12,0,0]。
本题可以简化为数组中的元素依次跟0进行比较，非0元素移动到数组前面，剩余的部分都是0。上述算法题的解法如下：
创建测试类用于验证移动零算法的功能，测试类如下：
执行测试代码，执行结果如下：
{0, 1, 0, 3, 12}移动零以后结果：
{1, 3, 12, 0, 0}
【算法题】
给定两个数组，编写一个函数计算两个数组的交集。
例如，输入array1=[1,2,3,4]，array2=[2,3]，输出[2,3]。
例如，输入array1=[1,2,3,4]，array2=[3,4,5]，输出[3,4]。
如果给定的数组已经排好序呢？你将如何优化算法？
本题提供两种解题思路。一种思路是假设两个数组都是无序的情况下，分别对数组中的元素进行计数，用另一个数组与之对比，出现相同的元素就加入交集中。另一种思路是假设在两个数组都是有序的前提下，只需同时遍历两个数组，相同的元素就加入交集中，否则继续向后搜索，直至结束。上述算法题的解法如下：
创建测试类用于验证求解两个数组交集的算法的功能，测试类如下：
执行测试代码，执行结果如下：
数组{1, 2, 3, 4}和数组{2, 3}的交集=[2, 3]
数组{1, 2, 3, 4}和数组{3, 4, 5}的交集=[3, 4]
【算法题】
给定一个未排序的数组，判断这个数组中是否存在长度为 3的递增子序列。
例如，输入数组[1,2,3,4,5]，输出true。
例如，输入数组[5,4,3,2,1]，输出false。
要求算法的时间复杂度为O(n)，空间复杂度为O(1)。
本题用两个变量分别记录最大值和最小值，如果出现比最大值还大的元素，就说明存在递增的三元子序列。上述算法题的解法如下：
创建测试类用于验证求递增三元子序列的算法的功能，测试类如下：
执行测试代码，执行结果如下：
数组{1,2,3,4,5}是否含有递增的三元子序列：true
数组{5,4,3,2,1}是否含有递增的三元子序列：false
【算法题】
本题提供两种解法：方法1是使用二分搜索，搜索数组的每一行；方法2是使用分治算法，不断缩小矩阵的规模。上述算法题的解法如下：
创建测试类用于验证搜索二维矩阵算法的功能，测试类如下：
执行测试代码，执行结果如下：
二维矩阵是否含有5：true
二维矩阵是否含有20：false
二维矩阵是否含有8：true
二维矩阵是否含有28：false
【算法题】
给定长度为n的整数数组，返回输出数组，其中每个元素等于原数组中除了自身以外的其他元素的乘积。
例如，输入数组[1,2,3,4]，输出数组[24,12,8,6]。
要求不使用除法。
本题可以使用左右两个数组left和right分别存储第i个元素左边的各个元素的乘积和第i个元素右边的各个元素的乘积，最终结果就是left和right两个数组对应位置两个元素的乘积生成的数组。
上述方法采用O(n)的时间复杂度和O(n)的空间复杂度，但O(n)的空间是可以省去的。使用两个变量就可以满足要求，使用变量left保存从左向右扫描数组A的乘积，使用变量right保存从右向左扫描数组A的乘积。
上述算法题的解法如下：
创建测试类用于验证算法的功能，测试类如下：
执行测试代码，执行结果如下：
数组{1, 2, 3, 4}除自身以外数组的乘积=24 12 8 6
数组{1, 2, 3, 4}除自身以外数组的乘积=24 12 8 6
除了本节介绍的相关的数组算法外，常见的数组相关算法还有很多，如数组排序、数组分割、最短无序子数组、山脉数组和数组拆分等。感兴趣的读者可以到互联网上搜索更多有关数组的算法。