常见算法总结 - 数组篇
程序员文章站
2022-05-04 11:04:18
1.给定一个数值在1 100的整数数组,请找到其中缺少的数字。 找到丢失的数字 利用byte数组的1或0标记该数字是否被删除,例如byte数组下标为0的数值为1的话,代表数字1存在 public static void findMissNumber2(int[] ints) { int sum = ......
1.给定一个数值在1-100的整数数组,请找到其中缺少的数字。
找到丢失的数字 利用byte数组的1或0标记该数字是否被删除,例如byte数组下标为0的数值为1的话,代表数字1存在
public static void findmissnumber1(int[] ints) { // 声明一个byte数组 byte[] isexist = new byte[100]; for (int i = 0; i < ints.length; i++) { // 由于数值比下标大1, 0位置其实代表的是数字1 isexist[ints[i] - 1] = 1; } for (int i = 0; i < isexist.length; i++) { if (isexist[i] == 0) { system.out.println("删除的数字是:" + ++i ); } } }
我们可以利用1-100的总和为5050,我们依次减掉数据内的所有值,得到的差值即为删除的值
public static void findmissnumber2(int[] ints) { int sum = 5050; for (int i = 0; i < ints.length; i++) { sum -= ints[i]; } system.out.println("删除的数字:" + sum); }
2.从数组中找出给定目标数字的两数组合。例如数组为{2, 3, 5, 7, 8, 9, 11, 14, 18},给定数字给17,那么数组内的3+14=17。
先利用set存储对应的数字,然后再遍历数组,假设遍历到数字3的时候,检查set中是否存在(17-3)=14这个数字,如果存在的话,即存在这个组合。
public static void findpairnumber(int[] arrays, int target) { set<integer> existintegers = new hashset<>(); for (int i = 0; i < arrays.length; i++) { existintegers.add(arrays[i]); } for (int i = 0; i < arrays.length; i++) { if (existintegers.contains(target - arrays[i])) { system.out.println("找到对应的数字组合:" + arrays[i] + "和" + (target - arrays[i])); // 去除掉已使用过的数字 existintegers.remove(arrays[i]); } } }
3.将数组进行反转。
只需要将数组按中间位置为对称轴进行位置交换即可
public static void reversearray(int[] arrays) { for (int i = 0; i < arrays.length/2; i++) { int tmp = arrays[i]; arrays[i] = arrays[arrays.length -1 - i]; arrays[arrays.length -1 - i] = tmp; } }
4.寻找数组中前k个最大的数。
我们新建一个长度为k的数组,遍历原数组,然后将大于k数组内的数字,放进k数组里,然后冒泡淘汰末尾的数字,最后剩下的就是前k个最大的数字。
public static int[] findkmaxints(int k, int[] ints) { int[] kints = new int[k]; for (int i = 0; i < ints.length; i++) { // 如果大于kints 数组中的最后一个数字的话,直接插入 if (ints[i] > kints[k - 1]) { kints[k - 1] = ints[i]; } // 再进行冒泡 bulb(kints); } return kints; } public static void bulb(int[] ints) { for (int i = ints.length-1; i >= 1; i--) { // 进行冒泡 if (ints[i] > ints[i - 1]) { int tmp = ints[i]; ints[i] = ints[i - 1]; ints[i-1]=tmp; } } }
5.求一个数组中连续子向量的最大和
遍历数组,从第一个大于0的数字开始累加,保存最大值,如果累加后的值小于等于0的话,就抛这一下标,从下一个下标开始累积,如果超过之前的最大值的话就进行替换。使用sum和max变量进行操作
public static integer findmaxsum(int[] ints) { if (ints.length == 0) { return null; } int currentsum = 0; int maxsum = 0; for (int i = 0; i < ints.length; i++) { currentsum += ints[i]; if (currentsum < 0) { currentsum = 0; } if (currentsum > maxsum) { maxsum = currentsum; } } return maxsum; }
6.一个数组中数字都两两重复,只有一个数字没有重复,如何找到那个数字?
我们可以将所有数字进行异或,两两重复的数字,都会被抵消掉,剩余最后的数字就是单个不重复的数字
public static integer findsinglenumber(int[] ints) { if (ints.length == 0) { return null; } int singlenumber = ints[0]; for (int i = 1; i < ints.length; i++) { singlenumber ^= ints[i]; } return singlenumber; }
7.将一个二维数组顺时针旋转90度.
先找出旋转90度,下标的变换规律。然后从外圈向内圈递归旋转变换。
public static void rollmatrix90(int[][] matrix, int circle) { // 当circle为0的时候为最外圈 if (matrix.length - circle * 2 <= 0) { return; } int bound = matrix.length - circle - 1; for (int i = circle; i < matrix.length - 1 - circle; i++) { int a = matrix[circle][i]; int b = matrix[i][bound]; int c = matrix[bound][bound - i + circle]; int d = matrix[bound - i + circle][circle]; matrix[circle][i] = d; matrix[i][bound] = a; matrix[bound][bound - i + circle] = b; matrix[bound - i + circle][circle] = c; } rollmatrix90(matrix, circle + 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,
翻转后的数组
21,16,11,6,1, 22,17,12,7,2, 23,18,13,8,3, 24,19,14,9,4, 25,20,15,10,5,
8.找出数组的中位数。
使用快排的思想,但是只往中间位置进行排序,当最后的排序下标抵达数组中间位置的时,就是中位数。
public static int findmiddlenumber(int[] array, int begin, int end) { int beginrange = begin; int endrange = end; if (begin >= end) { return begin; } // 选择begin位置的数字作为分界点 int splitnumber = array[begin]; while (begin + 1 < end) { if (array[begin + 1] < splitnumber) { begin++; continue; } if (array[end] > splitnumber) { end--; continue; } int tmp = array[begin + 1]; array[begin + 1] = array[end]; array[end] = tmp; } int tmp = array[beginrange]; array[beginrange] = array[begin]; array[begin] = tmp; if (begin > array.length / 2) { return findmiddlenumber(array, beginrange, begin); } else { return findmiddlenumber(array, end, endrange); } }
9.两个有序数组的合并排序
同时遍历两个数组,每次对比两个数组当前坐标的值哪个小,小的存入新的数组,数组下表往后移一位,大的那边坐标不变,继续下次大小对比。依次循环。
public static int[] mergesortarray(int[] arraya, int[] arrayb) { int[] sortarray = new int[arraya.length + arrayb.length]; int aindex = 0; int bindex = 0; for (int i = 0; i < sortarray.length && aindex <= arraya.length && bindex <= arrayb.length; i++) { if (aindex == arraya.length) { sortarray[i] = arrayb[bindex++]; continue; } if (bindex == arrayb.length) { sortarray[i] = arraya[aindex++]; continue; } if (arraya[aindex] < arrayb[bindex]) { sortarray[i] = arraya[aindex]; aindex++; } else { sortarray[i] = arrayb[bindex]; bindex++; } } return sortarray; }
本文转自我的个人博客:《coderv的进阶笔记》
欢迎加入java后端架构技术讨论群:1398880
我的公众号:coderv的进阶笔记,记录技术心得