java面试中常见的数组题目汇总（一）

package swear2offer.array; import java.util.Arrays; public class SortSequence { /** * 返回一个数字数组的排序值 * 比如数据 [6,2,5,0] 的返回是 [4,2,3,1] * */ public int[] compare(int[] a) { int i,j,n; n = a.length; int [] c = new int[n]; //数组下标从0开始，但是输出的次序从1开始，所以需要初始化数组为1 for (i=0; i
        

         登录后复制
        
       

6 6 2 6 2 5 6 2 5 0

/** * 这类要求空间O(1)时间复杂度为O(n)的问题 * 需要在一次遍历并且不声明新数组的情况下求解，这种题目通常要求元素大小跟下标大小一致。 * 所以通常考虑是利用数组存储的元素和数组下标来求解 * 在本题中，数组的元素变成了下标，而数组内元素则表示之前元素出现的次数，0则代表不出现。 * 为了区分元素和次数，可以把次数设定为负值 * */ public void Solution(int[] a) { int i,n,temp; n = a.length; i = 0; /** * 只有在temp小于0的时候才会推进循环 * */ while(i < n) { temp = a[i]-1; // 如果数组元素小于0，则代表该数已经被替换到其他地方或者已经被计数过从而被覆盖 if (temp < 0) { i ++; continue; } // 把未记录的数保存在已经记录的位置上，并用负值保存数量 if (a[temp]>0) { a[i] = a[temp]; a[temp] = -1; } else { a[i] = 0; //该数据已经使用过，且表示元素i+1出现0次 a[temp]--; } } }

package swear2offer.array; public class ArrayFind { /** * 在一个二维数组中（每个一维数组的长度相同）， * 每一行都按照从左到右递增的顺序排序， * 每一列都按照从上到下递增的顺序排序。 * 请完成一个函数，输入这样的一个二维数组和一个整数， * 判断数组中是否含有该整数。 * * 思路： * 从左上出发，需要考虑的情况太多，因为向右和向下都是递增 * 但是从右上出发，向左递减，向下递增，这样就把情况限定在一种。 * */ public boolean Find(int target, int [][] array) { int l,h,x,y; h = array.length; l = array[0].length; // 游标的横纵坐标 x = l-1; y = 0; while (x>=0 && y
        

         登录后复制
        
       

package swear2offer.array; public class Floors { /** * 一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。 * 求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。 * * 获取跳法次数 * */ public int JumpFloor(int target) { if (target < 3) return target; // 大于等于3个台阶，次数是第一步调1下和跳2下的个数之和 return JumpFloor(target-1) + JumpFloor(target-2); } }

package swear2offer.array; import java.util.Arrays; public class FloorsPlus { /** * 一只青蛙一次可以跳上 1 级台阶， * 也可以跳上 2 级…… 它也可以跳上 n 级。 * 求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 * * 动态规划：数组代表含义、边界、转换公式 * 动态规划最重要的是找出阶段之间的变化公式， * 即，n-1和n之间的状态是如何转移的 * * f[n]:n阶台阶的跳法 * f[n] = f[n-1]+f[n-2]+...+f[1]+f[0] * f[n-1]代表最后一步走了1步 * f[n-2]代表最后一步走了2步 * f[1]代表最后一步走了n-1步 * f[0]代表最后一步走了n步 * * 这里需要注意，f[0]=0,但是最后一步走了n步也算一种方法， * 所以需要初始化把数组初始化为1，或则单独处理f[0]. * * */ public int JumpFloorII(int target) { if (target < 3) return target; int[] f = new int[target+1]; //单独处理f[0] f[0] = 1; f[1] = 1;//边界 int i,j; for (i=2; i<=target; i++) { for (j=i-1; j>=0; j--) { f[i] += f[j]; } } return f[target]; } public int JumpFloorII2(int target) { if (target < 3) return target; int[] f = new int[target+1]; //初始化把数组初始化为1 Arrays.fill(f,1); f[0] = 0; f[1] = 1;//边界 int i,j; for (i=2; i<=target; i++) { for (j=i-1; j>0; j--) { f[i] += f[j]; } } return f[target]; } }