【算法】剑指offer-数组

数组

剑指 Offer 53 - II. 0～n-1中缺失的数字

数字与下标一一对应，利用二分查找，当缺失时下标与数字不同则找到

    public int missingNumber(int[] nums) {
        int left = 0, right = nums.length;
        int mid;
        while(left < right){
            mid = (right+left)>>>1;
            if(nums[mid] != mid) right = mid;
            else left = mid+1;
        }
        return left;
    }

剑指 Offer 53 - I. 在排序数组中查找数字 I

统计一个数字在排序数组中出现的次数。

二分查找target+0.5和target-0.5的位置，这俩之差就是次数

    public int search1(int[] nums, double target) {
        int l = 0, r = nums.length-1;
        int mid;
        while(l <= r){
            mid = (l + r) >>> 1;
            if(nums[mid] > target) r = mid - 1;
            else if(nums[mid] < target) l = mid + 1;
        }
        return l;
    }

剑指 Offer 29. 顺时针打印矩阵

动态设置边界

    public int[] spiralOrder(int[][] matrix) {
        if(matrix.length==0) return new int[0];
        int r=matrix[0].length-1, l=0, u=0, d=matrix.length-1, count=0;
        int [] res = new int [matrix.length * matrix[0].length];
        while(true){
            for(int col=l; col<=r; col++) res[count++]=matrix[u][col];
            // 走完从l→r后，改变上边界的值
            if(++u > d) break;
            for(int row=u; row<=d; row++) res[count++]=matrix[row][r];
            if(--r < l) break;
            for(int col=r; col>=l; col--) res[count++]=matrix[d][col];
            if(--d < u) break;
            for(int row=d; row>=u; row--) res[count++]=matrix[row][l];
            if(++l > r) break;
        }
        return res;
    }

剑指 Offer 04. 二维数组中的查找

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数

根据数组上到下，左到右逐渐增大的特性，故从左下角开始比较，较大则往右走，较小则往上走

    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int row,col,srow,scol,cur;
        srow = matrix.length - 1;
        scol = 0;
        while(srow >= 0 && scol < matrix[0].length){
            cur = matrix[srow][scol];
            if(target > cur)
                scol++;
            else if(target < cur)
                srow--;
            else
                return true;
        }
        return false;
    }

剑指 Offer 03. 数组中重复的数字

利用HashSet的add方法实现（set集合内不可重复）