1. 数组的改变和移动总结1.1 数组的改变
数组在内存中是一块连续的内存空间,我们可以直接通过下标进行访问,并进行修改。
在Java
中,对于List
类型来说,我们可以通过set(idx, element)
方法将idx
位置的元素进行修改。
1.2 数组的移动
数组的移动不能通过一条语句来实现,通常来说需要通过:插入、删除或者多次交换来实现。
1.3 数组的插入
数组的插入比较麻烦,我们想要在下标为k
的位置插入一个元素时,首先需要将k
及以后的元素往后移动一个位置,然后再将元素插入到k
的位置处。
在Java
中,对于List
类型来说,我们可以通过add(idx, element)
方法将元素添加到idx
下标处。
1.4 数组的删除
删除下标为k
的元素时,需要将k
以后的元素向前移动一个位置。
对于List
类型来说,我们可以通过remove(idx)
方法删除下标为idx
的元素。
2. 题目记录453. ⭐最小操作次数使数组元素相等分析题意
给你一个长度为n
的整数数组,每次操作将会使n - 1
个元素增加1
。返回让数组所有元素相等的最小操作次数。
思路分析
这道题有一个很巧妙的思路:由于我们并不关心最终元素相等时的值而只关心操作的次数。所以我们可以将上述问题转化为:每次操作使一个元素减少1
,返回让数组中所有元素相等的最小操作数。这样就简单了:我们想要操作数最小,就必须找到能使所有元素相等的最小值,其实这个值就是数组中的最小值。而操作的次数就是:每个数与最小值的差值之和。
class Solution { public int minMoves(int[] nums) { int min = Integer.MAX_VALUE; for(int i = 0; i < nums.length; i++){ min = Math.min(nums[i], min); } int ans = 0; for(int i = 0; i < nums.length; i++){ ans = ans + nums[i] - min; } return ans; }}
那么正向思考这个问题应该怎么做呢?
注意到:每次操作都使n-1
个数加1
,也就是所每次操作都会使该数组的sum
加上n-1
。假设最小操作数为a
次,那么此时一定有数学关系式:\(a(n-1) + sum = nx\),其中x
为最终数组中的值。
仅有这一个关系式的约束是不够的,我们还要想清楚的一点就是:原数组中最小的那个数需要操作a
次才能够变为x
,即:\(min + a = x\) (这个比较难想明白)
根据这两个公式我们就可以求出最终的a
了:\(a = sum – n * min\)
class Solution { public int minMoves(int[] nums) { int min = Integer.MAX_VALUE; int sum = 0; for(int i = 0; i < nums.length; i++){ sum += nums[i]; min = Math.min(nums[i], min); } return sum - nums.length * min; }}
复杂度分析
时间复杂度:O(n)
空间复杂度:O(1)
665. 非递减数列分析题意
给你一个长度为n
的整数数组nums
,请你判断在最多改变1
个元素的情况下,该数组能否变成一个非递减数列。
思路分析
从前往后遍历,找到第一个 a > b
的情况时,对a
或 b
的值进行修改,然后判断修改后的数组是否为非递减数组即可。关键在于:修改 a
还是 修改 b
呢?
这里其实是有两个选择的:
- 对于 [1, 3, 4, 2, 5] ,此时应该修改
b
; - 对于[1, 3, 4, 3, 4], 此时应该修改
a
;
一种简单的方法就是:我们两种情况都尝试,看看是否能够得到非递减数组。
class Solution { public boolean checkPossibility(int[] nums) { for(int i = 0; i nums[i + 1]){ int n_1 = nums[i]; int n_2 = nums[i + 1]; // 修改a nums[i] = n_2; if(checkMethod(nums)) return true; // 复位a nums[i] = n_1; // 修改b nums[i + 1] = n_1; if(checkMethod(nums)) return true; return false; } } return true; } boolean checkMethod(int[] nums){ for(int i = 1; i nums[i]) return false; } return true; }}
复杂度分析
时间复杂度:O(n)
空间复杂度:O(1)
283. 移动零分析题意
给定一个数组nums
,编写一个函数将所有0
移动到数组的末尾,同时保持非零元素的相对顺序。
请注意,必须在不复制数组的情况下原地对数组进行操作。
关键点:保持非零元素的相对顺序。
思路分析
首先排除首尾双指针的思路,因为要保持非零元素的相对顺序,所以不能够使用首尾双指针来做。
首尾双指针是指:左指针找第一个0元素,右指针找第一个非0元素,然后交换两个元素。有点像归并排序。
由于不复制数组,所以大概率还是使用双指针来操作。分析一下,假设我们知道left
左侧都是非零元素,然后在left
右侧找到了一个非零元素,此时只需要将该元素放在left
下标下即可。
基于此思路,我们用left
来标识已经处理元素的右边界,然后通过右指针去寻找下一个非0元素,找到后放置在left
位置并将left
指针右移。
class Solution { public void moveZeroes(int[] nums) { int left = 0; int right = 0; while(right < nums.length){ if(nums[right] != 0){ nums[left] = nums[right]; left ++; } right ++; } while(left < nums.length){ nums[left] = 0; left ++; } }}
复杂度分析
时间复杂度:O(n)
空间复杂度:O(1)
本文来自博客园,作者:睡觉不打呼,转载请注明原文链接:https://www.cnblogs.com/404er/p/array_move.html