本文总结:
1、数组运算
- 三个数最大乘积
2、数组统计
- 使用Map或者Set来实现。比如重复、丢失。
- 快排。比如H指数等。
3、数组移动
- 旋转数组，考虑冒泡，来实现O(1)空间移动元素。
- 移动最小次数使数组元素一样
4、数组乘积
- 除自身以外的数组乘积。
- 区域和检索 – 数组不可变。 k-n的和为sum(n)-sum(k)
1 常用算法
1.1 二分查找相关
1.2 冒泡
常用在数组移动操作中
|
1 2 3 4 5 6 |
private void swap(int[] nums,int beg,int end){ for(int i=beg;i<end;i++){ int temp = nums[i]; nums[i] = nums[i+1]; nums[i+1] =temp; } |
2 数组遍历
2.1 报数
有 10个人围成一个圈，从 1 开始报数，报到 4 的这个人就要退出。然后其他人重新开始， 从 1 报数，到 4 退出。问：最后剩下的是 10 人中的第几个人？
中止：list.size == 1
部分中止：i%4==0
发现4之后：使用数组的remove方法。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
public class Baoshu { public static void main(String[] args){ List<Integer> input = Lists.newArrayList(1,2,3,4,5,6,7,8,9,10); System.out.println(find(input)); } public static int find(List<Integer> input){ if(input.size() == 1){ return input.get(0); } // 1 报数 int count =1; int index=0; while (true){ if(input.size() == 1){ return input.get(0); } // 2 重置index index = index%input.size(); if(count%4==0){ input.remove(index); }else { // 3没有到4的,index++。如果到4不执行这个操作,只执行remove index++; } count++; } } } |
执行结果:5
2.2 最大连续1的数
给定一个二进制数组， 计算其中最大连续1的个数。
示例 1:
输入: [1,1,0,1,1,1]
输出: 3
解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/max-consecutive-ones
算法：需要考虑只有一个元素情况，后者结尾依然是1的情况
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Solution { // 需要考虑只有一个元素情况，后者结尾依然是1的情况 public int findMaxConsecutiveOnes(int[] nums) { if(nums==null || nums.length ==0){ return 0; } int max= 0; int count = 0; for(int i=0;i<nums.length;i++){ if(nums[i] == 1){ count++; }else{ if(count>max){ max =count; } count =0; } } // 需要考虑只有一个元素情况，后者结尾依然是1的情况 return Math.max(max,count); } } |
2.3 提莫攻击
在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄，他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。现在，给出提莫对艾希的攻击时间序列和提莫攻击的中毒持续时间，你需要输出艾希的中毒状态总时长。
你可以认为提莫在给定的时间点进行攻击，并立即使艾希处于中毒状态。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/teemo-attacking
|
1 2 3 4 5 6 |
输入: [1,2], 2 输出: 3 原因: 第 1 秒初，提莫开始对艾希进行攻击并使其立即中毒。中毒状态会维持 2 秒钟，直到第 2 秒末结束。 但是第 2 秒初，提莫再次攻击了已经处于中毒状态的艾希。 由于中毒状态不可叠加，提莫在第 2 秒初的这次攻击会在第 3 秒末结束。 所以最终输出 3 。 |
算法：
- 末尾处理还得+duration
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class Solution { public int findPoisonedDuration(int[] timeSeries, int duration) { if(timeSeries ==null || timeSeries.length ==0 ){ return 0; } int time =0; for(int i=0;i<timeSeries.length;i++){ // 末尾处理 if(i == timeSeries.length-1){ time+=duration; return time; }else{ time += Math.min(duration,timeSeries[i+1]-timeSeries[i]); } } return time; } } |
2.4 第三大数
给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
|
1 2 3 4 5 6 |
输入: [2, 2, 3, 1] 输出: 1 解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。 存在两个值为2的数，它们都排第二。 |
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/third-maximum-number
算法1 : 优先级队列和hashset。
- 第K大，使用优先级队列。
- 防重使用HashSet
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
class Solution { public int thirdMax(int[] nums) { if(nums ==null || nums.length ==0){ return -1; } PriorityQueue<Integer> p = new PriorityQueue<Integer>(new Comparator<Integer>(){ public int compare(Integer o1,Integer o2){ // 考虑边界 if(o1 == Integer.MIN_VALUE || o2==Integer.MAX_VALUE){ return 1; } if(o2 == Integer.MIN_VALUE || o1==Integer.MAX_VALUE){ return -1; } return o2 - o1; } }); Set<Integer> dic = new HashSet<Integer>(); for(int i=0; i<nums.length;i++){ if(dic.contains(nums[i])){ continue; } dic.add(nums[i]); p.add(nums[i]); } if(dic.size()<3){ return p.poll(); } for(int i=0;i<2;i++){ p.poll(); } return p.poll(); } } |
算法2 三个变量
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class Solution { public int thirdMax(int[] nums) { long first = Long.MIN_VALUE; long second = Long.MIN_VALUE; long third = Long.MIN_VALUE; for (int num : nums) { if(num>first){ third = second; second = first; first = num; }else if(num>second&&num<first){ third = second; second = num; }else if(num<second&&num>third){ third = num; } } return third!=Long.MIN_VALUE ? new Long(third).intValue() : new Long(first).intValue(); } } |
2.5 三个最大积
给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
示例 1:
|
1 2 |
<strong>输入:</strong> [1,2,3] <strong>输出:</strong> 6 |
链接：https://leetcode-cn.com/problems/maximum-product-of-three-numbers/
算法：
- 最大积有三种情况，直接获取这三种情况最大值
- 快排时，注意break；
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
class Solution { // 三种情况最大值 public int maximumProduct(int[] nums) { // 条件判断 if(nums == null || nums.length<3){ return -1; } // 快排 quickSort(nums,0,nums.length -1); int length = nums.length; // 对应三种情况 int max = Math.max(nums[length-1]*nums[length-2]*nums[length-3],nums[0]*nums[1]*nums[length-1]); max = Math.max(max,nums[0]*nums[1]*nums[2]); return max; } public void quickSort(int[] nums,int beg,int end){ if(beg>=end){ return; } int mark = nums[beg]; int left = beg; int right = end; while (left<right){ while(left<right){ if(nums[right] < mark){ nums[left] = nums[right]; left++; // 中止break break; }else{ right--; } } while(left<right){ if(nums[left] >= mark){ nums[right] = nums[left]; right--; // 中止break break; }else{ left++; } } } nums[left] = mark; quickSort(nums,beg,left-1); quickSort(nums,left+1,end); } } |
2.6 除自身以外数组的乘积
给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例:
输入: [1,2,3,4]
输出: [24,12,8,6]
来源：力扣（LeetCode）
链接：http://：https://leetcode-cn.com/problems/product-of-array-except-self
算法思想：构造两个数组，一个保存元素左边的乘积，一个保存元素右边乘积。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
class Solution { public int[] productExceptSelf(int[] nums) { if(nums ==null){ return null; } int length = nums.length; int[] l = new int[length]; int[] r= new int[length]; for(int i=0;i<length;i++){ if(i==0){ l[i] = 1; }else{ l[i] = nums[i-1]*l[i-1]; } } for(int j=length-1;j>=0;j--){ if(j==length-1){ r[j] = 1; }else{ r[j] = nums[j+1]*r[j+1]; } } int[] result = new int[length]; for(int i=0;i<length;i++){ result[i]=l[i]*r[i]; } return result; } } |
2.7 区域和检索 – 数组不可变
给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。
链接：https://leetcode-cn.com/problems/range-sum-query-immutable/
算法思想： k-n的和为sum(n)-sum(k)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
private int[] sum; public NumArray(int[] nums) { sum = new int[nums.length + 1]; for (int i = 0; i < nums.length; i++) { sum[i + 1] = sum[i] + nums[i]; } } public int sumRange(int i, int j) { return sum[j + 1] - sum[i]; } 作者：LeetCode 链接：https://leetcode-cn.com/problems/range-sum-query-immutable/solution/qu-yu-he-jian-suo-shu-zu-bu-ke-bian-by-leetcode/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 |
3 数组运算
3.1 两数求和
问题：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
参考：https://leetcode-cn.com/problems/two-sum
举例：
|
1 2 3 4 |
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] |
算法实现：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution { // map的containsKey public int[] twoSum(int[] nums, int target) { Map<Integer,Integer> dic = new HashMap<Integer,Integer> (); for(int i=0;i<nums.length;i++){ dic.put(nums[i],i); } int[] result = new int[2]; for(int j=0;j<nums.length;j++){ int selectKey = target - nums[j]; // 需要添加dic.get(selectKey)!=j if(dic.containsKey(selectKey) && dic.get(selectKey)!=j){ result[0] = j; result[1] = dic.get(selectKey).intValue(); return result; } } return null; } } |
4 数组合并
4.1 合并有序数组
输入两个有序数组，合并成一个有序数组
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
public class MergeArray { public List<Integer> merge(List<Integer> input1,List<Integer> input2) { List<Integer> mResult = new ArrayList<Integer>(); merge(input1,0,input2,0,mResult); return mResult; } private void merge(List<Integer> input1, int beg1, List<Integer> input2, int beg2, List<Integer> mResult) { if (beg1 >= input1.size() && beg2 >= input2.size()) { return; } if (beg1 < input1.size() && beg2 < input2.size()) { if (input1.get(beg1) < input2.get(beg2)) { mResult.add(input1.get(beg1)); merge(input1, beg1 + 1, input2, beg2, mResult); } else { mResult.add(input2.get(beg2)); merge(input1, beg1, input2, beg2 + 1, mResult); } } else if (beg1 < input1.size()) { mResult.add(input1.get(beg1)); merge(input1, beg1 + 1, input2, beg2, mResult); } else if (beg2 < input2.size()) { mResult.add(input2.get(beg2)); merge(input1, beg1, input2, beg2 + 1, mResult); } } public static void main(String[] args) { List<Integer> input1 = Arrays.asList(1, 2); List<Integer> input2 = Arrays.asList(3, 4); MergeArray fid = new MergeArray(); System.out.println(fid.merge(input1, input2)); } } |
5 数组元素统计
5.1 数组中重复的和缺失的数
用到方法有：HashSet/HashMap/快排
5.1.1 查找重复和缺失数
集合 S 包含从1到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。
给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
示例 1:
输入: nums = [1,2,2,4]
输出: [2,3]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/set-mismatch
算法：通过set来记录多余元素，并通过set来检查缺失元素
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Solution { // 连续数组。查找丢失和重复数 public int[] findErrorNums(int[] nums) { Set<Integer> dic = new HashSet<Integer>(); int[] result = new int[2]; for(int i=0;i<nums.length;i++){ if(dic.contains(nums[i])){ result[0] = nums[i]; continue; } dic.add(nums[i]); } for(int i=1;i<=nums.length;i++){ if(!dic.contains(i)){ result[1]=i; break; } } return result; } } |
5.3.2 查找缺失数
给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array
算法：使用用HashSet记录1到n出现的数，然后扫描1到n的数，看那些没有在set中。代码类似5.1.1
5.3.4 缺失的第一个正数
给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
示例 1:
|
1 2 |
输入: [1,2,0] 输出: 3 |
算法：
- 考虑。数组值是1-n。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Solution { public int firstMissingPositive(int[] nums) { if(nums==null || nums.length==0){ return 1; } Set<Integer> dic = new HashSet<Integer>(); for(int i=0;i<nums.length;i++) { if(!dic.contains(nums[i])){ dic.add(nums[i]); } } for(int i=1;i<=nums.length;i++){ if(!dic.contains(i)){ return i; } } // 这种场景要考虑。数组值是1-n。 return nums.length+1; } } |
5.1.3 数组重复的数据
给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。
找到所有出现两次的元素。
你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-all-duplicates-in-an-array
算法: 先快排，再遍历数组。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class Solution { public List<Integer> findDuplicates(int[] nums) { List<Integer> result = new ArrayList(); quickSort(nums,0,nums.length-1); for(int i=1;i<nums.length; i++){ if(nums[i-1]==nums[i]){ result.add(nums[i]); } } return result; } public void quickSort(int[] nums,int beg,int end){ 快排 } } |
5.1.4 H数
给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 h 指数。
h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。（其余的 N – h 篇论文每篇被引用次数 不超过 h 次。）
例如：某人的 h 指数是 20，这表示他已发表的论文中，每篇被引用了至少 20 次的论文总共有 20 篇。
示例：
输入：citations = [3,0,6,1,5]
输出：3
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/h-index
算法：
- 第一步 快排。
- 第二步 计算H参数：如果h为5，那么倒数第5篇的引用肯定要大于5的。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
class Solution { // H 就是满足条件文章数。 // 计算H参数：如果h为5，那么倒数第5篇的引用肯定要大于5的。 public int hIndex(int[] nums) { if(nums==null || nums.length==0){ return 0; } // 快排-升序 int length = nums.length; quickSort(nums,0,length-1); // 计算H参数：如果h为5，那么倒数第5篇的引用肯定要大于5 for(int i = length ;i>0;i--){ if(nums[length-i]>=i){ return i; } } return 0; } public void quickSort(int[] nums,int beg,int end){ if(beg>=end){ return; } int mark = nums[beg]; int left = beg; int right = end; while (left<right){ while(left<right){ if(nums[right] < mark){ nums[left] = nums[right]; left++; // 中止break break; }else{ right--; } } while(left<right){ if(nums[left] >= mark){ nums[right] = nums[left]; right--; // 中止break break; }else{ left++; } } } nums[left] = mark; quickSort(nums,beg,left-1); quickSort(nums,left+1,end); } } |
5.2 数组度
给定一个非空且只包含非负数的整数数组 nums, 数组的度的定义是指数组里任一元素出现频数的最大值。
你的任务是找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
示例 1:
输入: [1, 2, 2, 3, 1]
输出: 2
解释:
输入数组的度是2，因为元素1和2的出现频数最大，均为2.
连续子数组里面拥有相同度的有如下所示:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短连续子数组[2, 2]的长度为2，所以返回2.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/degree-of-an-array
算法 ：
- 作为数组的度的元素，只需要统计这个元素的开始和结束位置，就是这个元素最小子数组的长度。使用三个map来保存这些信息
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
class Solution { public int findShortestSubArray(int[] nums) { if(nums == null || nums.length<=1){ return nums.length; } // 三个map Map<Integer,Integer> duDic = new HashMap<Integer,Integer>(); Map<Integer,Integer> indexDic = new HashMap<Integer,Integer>(); Map<Integer,Integer> lenDic = new HashMap<Integer,Integer>(); for(int i=0;i<nums.length;i++){ if(duDic.containsKey(nums[i])){ duDic.put(nums[i],duDic.get(nums[i])+1); lenDic.put(nums[i],i-indexDic.get(nums[i])+1); }else{ duDic.put(nums[i],1); indexDic.put(nums[i],i); lenDic.put(nums[i],1); } } // 获取数组度 int duArray = 1; for(Integer du : duDic.values() ){ if(du>duArray){ duArray = du; } } // 获取最下子数组长度 int result = Integer.MAX_VALUE; for(Map.Entry<Integer,Integer> entry:duDic.entrySet()){ if(entry.getValue() == duArray){ result = Math.min(result,lenDic.get(entry.getKey())); } } return result; } } |
6 数组移动
6.1 最小移动次数使数组元素相等
给定一个长度为 n 的非空整数数组，找到让数组所有元素相等的最小移动次数。每次移动将会使 n – 1 个元素增加 1。
示例:
输入:
[1,2,3]
输出:
3
解释:
只需要3次移动（注意每次移动会增加两个元素的值）：
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-moves-to-equal-array-elements
算法
- 查找最小值
- 依次累加每个元素和最小元素差值。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution { public int minMoves(int[] nums) { int moves = 0, min = Integer.MAX_VALUE; for (int i = 0; i < nums.length; i++) { min = Math.min(min, nums[i]); } for (int i = 0; i < nums.length; i++) { moves += nums[i] - min; } return moves; } } |
6.2 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/move-zeroes
算法： 冒泡的思想，从后遍历数组，发现0，就向右依次冒泡。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Solution { // 冒泡 public void moveZeroes(int[] nums) { int end = nums.length -1; for(int z=nums.length-1;z>=0;z--){ if(nums[z]==0){ // 执行冒泡 swap(nums,z,end); end--; } } } private void swap(int[] nums,int beg,int end){ for(int i=beg;i<end;i++){ int temp = nums[i]; nums[i] = nums[i+1]; nums[i+1] =temp; } } } |
6.3 删除一个元素实现非递减
算法思想：找到第一个有问题节点，然后分为两种情况：删除前一个节点和删除当前节点来处理
- 删除前一个节点和删除当前节点来处理可以通过逻辑删除来实现。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
class Solution { // 算法：找到第一个有问题节点，然后分为两种情况：删除前一个节点和删除当前节点来处理 // 删除前一个节点和删除当前节点来处理可以通过逻辑删除来实现。 public boolean checkPossibility(int[] nums) { if(nums ==null || nums.length<=2){ return true; } int i=1; for(; i< nums.length;i++){ if(nums[i]<nums[i-1]){ break; } } int copy=nums[i-1]; // 2 分为两种情况： // 2.1 删除前一个节点 if(i-2>=0){ nums[i-1]=nums[i-2]; // 删除前一个节点 }else{ nums[i-1]=Integer.MIN_VALUE; } boolean result = check(nums,i); if(result){ return true; }else { nums[i-1] = copy; } // 2.2 删除当前节点和 nums[i]=nums[i-1]; // 表示删除当前节点 result = check(nums,i); return result; } private boolean check(int[] nums,int beg){ for(int i=beg;i<nums.length;i++){ if(nums[i]<nums[i-1]){ return false; } } return true; } } |
7 数组旋转
7.1 旋转指定k的数组
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: [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]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-array
算法：使用冒泡移动数组，循环从0开始执行冒泡，循环次数由k决定。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
class Solution { public void rotate(int[] nums, int k) { if(nums==null || nums.length<=1){ return; } int position = k % nums.length; if(position ==0){ return; } position = nums.length - position; for(int i=0;i<position;i++){ // 冒泡起始为0 swap(nums,0,nums.length-1); } } private void swap(int[] nums,int beg,int end){ for(int i=beg;i<end;i++){ int temp = nums[i]; nums[i] = nums[i+1]; nums[i+1] =temp; } } } |
