2025年数组题库及答案

2025年数组题库及答案一、基础操作题1.问题描述：给定一个长度为n的整数数组arr（n≥5），要求在索引k（2≤k≤n-2）处插入一个新元素x，使得插入后的数组长度为n+1。若k超出有效范围（k<0或k≥n），则返回原数组。输入示例：arr=[3,1,4,1,5],k=2,x=9输出示例：[3,1,9,4,1,5]解题步骤：检查k是否在0到n-1之间（原数组长度为n），若否直接返回原数组。创建新数组new_arr，长度为n+1。将原数组前k个元素复制到new_arr的前k位置。新元素x放入new_arr的第k位。将原数组从k到n-1的元素复制到new_arr的k+1到n位置。2.问题描述：已知数组nums=[5,2,7,2,9,5]，要求删除所有值为val（val=5）的元素，返回删除后的数组长度及新数组。需原地修改数组，空间复杂度O(1)。输入示例：nums=[5,2,7,2,9,5],val=5输出示例：长度3，数组[2,7,2]解题思路：使用双指针法，左指针i记录有效元素位置，右指针j遍历数组。当nums[j]≠val时，将nums[i]赋值为nums[j]，i右移。最终i即为新数组长度，数组前i个元素为有效部分。3.问题描述：给定数组arr=[1,3,5,7,9]，要求将其反转。需原地操作，不使用额外数组。输入示例：[1,3,5,7,9]输出示例：[9,7,5,3,1]解题步骤：初始化左指针left=0，右指针right=arr.length-1。交换arr[left]与arr[right]，left右移，right左移，直到left≥right。二、中级算法题4.问题描述：给定无序数组nums=[-2,1,-3,4,-1,2,1,-5,4]，求其连续子数组的最大和。要求时间复杂度O(n)。输入示例：[-2,1,-3,4,-1,2,1,-5,4]输出示例：6（对应子数组[4,-1,2,1]）解题思路（动态规划）：定义dp[i]为以nums[i]结尾的连续子数组最大和。状态转移方程：dp[i]=max(nums[i],dp[i-1]+nums[i])。初始条件dp[0]=nums[0]，遍历数组更新dp数组，记录最大值。5.问题描述：给定排序数组nums=[1,2,3,4,5,6,7]，要求找到两个数，使得它们的和等于目标数target=9，返回这两个数的索引（索引从1开始）。假设每个输入仅对应唯一解，且不能重复使用同一个元素。输入示例：nums=[1,2,3,4,5,6,7],target=9输出示例：[2,7]（对应元素2和7，索引2和7）解题思路（双指针法）：左指针left=0，右指针right=nums.length-1。计算当前和sum=nums[left]+nums[right]。若sum<target，left右移；若sum>target，right左移；若相等则返回[left+1,right+1]。6.问题描述：给定数组prices=[7,1,5,3,6,4]，表示某股票第i天的价格。设计算法计算能获得的最大利润，最多允许完成一次交易（买入后卖出一次）。输入示例：[7,1,5,3,6,4]输出示例：5（第2天买入，第5天卖出，利润6-1=5）解题思路：遍历数组，记录当前最小价格min_price（初始为prices[0]）。计算当前价格与min_price的差值，记录最大差值max_profit。7.问题描述：给定数组arr=[3,1,4,1,5,9,2,6]，要求找出其中第k大的元素（k=3）。注意：第k大是指从大到小排序后的第3个元素（非索引）。输入示例：arr=[3,1,4,1,5,9,2,6],k=3输出示例：6（排序后[9,6,5,4,3,2,1,1]，第3大是5？需修正：原数组排序后为[9,6,5,4,3,2,1,1]，第1大9，第2大6，第3大5，故正确输出应为5）解题步骤（快速选择算法）：利用快速排序的分区思想，选择基准pivot，将数组分为大于pivot和小于pivot两部分。若基准位置等于n-k（n为数组长度），则该位置元素即为第k大。否则根据基准位置调整搜索区间，直到找到目标位置。三、高级技巧题8.问题描述：给定二维数组matrix=[[1,2,3],[4,5,6],[7,8,9]]，要求顺时针旋转90度。需原地旋转，不使用额外空间。输入示例：[[1,2,3],[4,5,6],[7,8,9]]输出示例：[[7,4,1],[8,5,2],[9,6,3]]解题步骤：先转置矩阵（行变列）：原matrix[i][j]变为matrix[j][i]，得到[[1,4,7],[2,5,8],[3,6,9]]。对每一行进行反转，第一行[1,4,7]反转后[7,4,1]，第二行[2,5,8]反转后[8,5,2]，第三行[3,6,9]反转后[9,6,3]。9.问题描述：给定数组nums=[2,3,1,2,4,3]，找出长度最小的连续子数组，其和≥target=7。输入示例：nums=[2,3,1,2,4,3],target=7输出示例：2（子数组[4,3]长度2，和为7）解题思路（滑动窗口）：初始化左指针left=0，当前和sum=0，最小长度min_len=无穷大。右指针right遍历数组，sum+=nums[right]。当sum≥target时，尝试收缩左指针：sum-=nums[left]，left右移，同时更新min_len为right-left+1的最小值。10.问题描述：给定数组candidates=[2,3,6,7]，目标数target=7，找出所有和为target的唯一组合（candidates中的元素可重复使用）。输入示例：candidates=[2,3,6,7],target=7输出示例：[[2,2,3],[7]]解题思路（回溯法）：排序数组，避免重复组合。递归函数参数：当前组合、剩余目标值、起始索引（避免重复选择之前元素）。若剩余目标值为0，将当前组合加入结果；若剩余目标值<0，回溯。遍历从起始索引开始的元素，将当前元素加入组合，递归调用（允许重复，故起始索引不变），然后回溯（移除当前元素）。11.问题描述：给定数组nums=[1,2,3,4,5,6,7]，要求将其重新排列为nums[0]<nums[1]>nums[2]<nums[3]>…的摆动序列。输入示例：[1,2,3,4,5,6,7]输出示例：[2,3,1,5,4,7,6]（或其他符合条件的排列）解题步骤（贪心算法）：将数组排序为升序。从中间位置分割为两部分，前半部分small=[1,2,3]，后半部分large=[4,5,6,7]。逆序合并：先取small最后一个，再取large最后一个，交替插入。例如：small逆序[3,2,1]，large逆序[7,6,5,4]，合并得到[3,7,2,6,1,5,4]，调整后满足摆动条件。12.问题描述：给定数组arr=[0,1,0,3,12]，要求将所有0移动到数组末尾，同时保持非零元素的相对顺序。需原地操作。输入示例：[0,1,0,3,12]输出示例：[1,3,12,0,0]解题思路：使用指针i记录非零元素的位置，遍历数组。当遇到非零元素时，将arr[i]与当前元素交换，i右移。遍历结束后，i到数组末尾的元素全部置0。四、综合应用题13.问题描述：某电商平台记录了一周内每天的订单量数组orders=[120,80,150,90,200,180,160]，要求计算：（1）订单量的中位数；（2）连续3天订单量的最大和；（3）若订单量超过170为“高峰日”，统计高峰日的数量。输入示例：orders=[120,80,150,90,200,180,160]输出示例：（1）150；（2）540（第5、6、7天：200+180+160=540？实际计算：窗口1:120+80+150=350；窗口2:80+150+90=320；窗口3:150+90+200=440；窗口4:90+200+180=470；窗口5:200+180+160=540，故最大和为540）；（3）2（200和180）。解题步骤：（1）排序数组[80,90,120,150,160,180,200]，中位数为第4个元素150。（2）滑动窗口计算连续3天和，记录最大值。（3）遍历数组，统计大于170的元素个数。14.问题描述：给定数组gas=[3,1,2,4,5]，cost=[2,2,3,3,4]，表示加油站i的油量和到达下一站的耗油量。若存在起点可以绕环一周，返回最小起点索引；否则返回-1。输入示例：gas=[3,1,2,4,5],cost=[2,2,3,3,4]输出示例：3（从索引3出发，剩余油量4-3=1→5-4=1+1=2→3-2=2+2=4→1-2=4+1=5→2-3=5+2=4→4-3=4+4=8，绕完一周）解题思路：计算每个站点的净油量gas[i]-cost[i]，若总和<0则无解。遍历数组，维护当前剩余油量current_tank和总剩余油量total_tank，记录可能的起点start。若current_tank<0，重置current_tank为0，start=下一个索引，否则current_tank+=gas[i]-cost[i]。最终若total_tank≥0，返回start。15.问题描述：给定二维数组grid=[[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]，其中1表示陆地，0表示水域。求最大的岛屿面积（相连的陆地视为同一岛屿，四方向相邻）。输入示例：grid=[[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]输出示例：4（第三行的[0,1,1,1]与第二行的1不相连？实际遍历：第一行前两格1相连，面积2；第二行第一个1与第一行第一个1相连，面积+1=3；第二行最后一个1单独，面积1；第三行中间三个1相连，面积3；第三行最后一个1与第二行最后一个1不相连；第四行第一个1与第二行第一个1相连，面积+1=4；第四行第三个1与第三行第三个1相连，面积+1=4。故最大面积为4）解题步骤（深度优先搜索）：遍历每个格子，若为陆地且未被访问过，进行DFS。DFS中标记已访问的格子，向四方向扩展，统计当前岛屿面积。记录所有岛屿面积的最大值。16.问题描述：给定数组nums=[4,5,6,7,0,1,2]（旋转排序数组，原排序为[0,1,2,4,5,6,7]，在索引3处旋转），要求搜索目标数target=0，返回其索引；若不存在返回-1。输入示例：nums=[4,5,6,7,0,1,2],target=0输出示例：4解题思路（二分查找）：确定中点mid，判断左半部分或右半部分是否有序。若左半部分有序且target在左半区间，调整右边界；否则调整左边界。若nums[mid]==target，返回mid；若左右边界交叉，返回-1。17.问题描述：给定数组nums=[3,2,2,3]，val=3，要求移除所有值为val的元素，并返回新数组的长度。需原地修改，元素顺序可变，不考虑新数组中超出长度的元素。输入示例：nums=[3,2,2,3],val=3输出示例：2（新数组前两个元素为[2,2]）解题步骤（双指针优化）：左指针i=0，右指针j=nums.length-1。当i≤j时，若nums[i]==val，将nums[i]与nums[j]交换，j左移；否则i右移。最终i即为新数组长度。18.问题描述：给定数组arr=[1,3,2,2,5,2,3,7]，要求找出出现次数超过一半的元素（多数元素）。假设数组非空且多数元素存在。输入示例：arr=[1,3,2,2,5,2,3,7]（实际多数元素需出现次数>4次，此示例中2出现3次，不符合条件，需调整示例为arr=[2,2,1,1,1,2,2]，则2出现4次，总长度7，4>3.5，符合条件）修正输入示例：arr=[2,2,1,1,1,2,2]输出示例：2解题思路（摩尔投票法）：初始化候选元素candidate=arr[0]，计数count=1。遍历数组，若当前元素==candidate，count+1；否则count-1。若count=0，更新candidate为当前元素，count=1。最终candidate即为多数元素。19.问题描述：给定数组heights=[0,1,0,2,1,0,1,3,2,1,2,1]，表示直方图的高度，计算下雨后能接多少雨水。输入示例：heights=[0,1,0,2,1,0,1,3,2,1,2,1]输出示例：6（具体计算：索引2处接1（左最高1，右最高2，min=1-0=1）；索引4处接1（左最高2，右最高3，min=2-1=1）；索引5处接2（左最高2，右最高3，min=2-0=2）；索引9处接1（左最高3，右最高2，min=2-1=1；但实际正确计算为：各位置积水量=min(左最大,右最大)-当前高度。左最大数组[