剑指offer题解—数组

之前都只是单纯的刷刷题,但是效果有限,今天开始更题解,希望别这么菜了233~
这部分主要以牛客上的题为主,leetcode上大同小异,只是输出有些不同。

【牛客】二维数组的查找

题目描述

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

Consider the following matrix:
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.
Given target = 20, return false.

思路

public class Solution {
    public boolean Find(int target, int [][] array) {
        /*
        if (array.length == 0)
            return false;
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                if (array[i][j] == target)
                    return true;
            }
        }
        return false;
        */

        if (array.length == 0) return false;
        for (int i = 0; i < array.length; i++) {
            if (binarySearch(array[i],target))
                return true;
        }
        return false;
    }
    public boolean binarySearch(int[] nums , int target){
        int l = 0;
        int r = nums.length-1;
        while (l <= r){
            int mid = (l+r)>>1;
            if (nums[mid] == target)
                return true;
            if (nums[mid] > target)
                r = mid-1;
            if (nums[mid] < target)
                l = mid+1;
        }
        return false;
    }
}
  1. 最容易的思路就是暴力,时间复杂度N*N
public boolean Find(int target, int [][] array) {
        for (int i = 0 ; i < array.length ; i++)
            for (int j = 0 ; j < array[i].length ; j++)
                if (array[i][j] == target)
                    return true;
        return false;
    }
  1. 由于每行都是递增的,可以对每一行分别进行二分查找。时间复杂度为N*logN
public boolean Find(int target, int [][] array) {
        for ( int i = 0 ; i < array.length ; i++)
            if(BianrySearch(target , array[i]))
                return true;
        return false;
    }

    public boolean BianrySearch(int target , int[] nums){
        if (nums.length == 0) return false;
        int l = 0;
        int r = nums.length - 1;
        while( l <= r){
            int mid  = ( l + r ) >> 1;
            if ( nums[mid] == target )
                return true;
            else if ( nums[mid] > target )
                r = mid - 1;
            else 
                l = mid + 1;
        }
        return false;
  1. 该二维数组中的一个数,小于它的数一定在其左边,大于它的数一定在其下边。因此,从右上角开始查找,就可以根据 target 和当前元素的大小关系来缩小查找区间,当前元素的查找区间为左下角的所有元素。

    时间复杂度 O(M + N),空间复杂度 O(1)。其中 M 为行数,N 为 列数。

public boolean Find(int target, int [][] array) {
        if (array == null || array.length == 0 || array[0].length == 0) return false;
        int cols = array[0].length;//列数
        int rows = array.length; //行数
        //从右上角开始
        int r = 0; //第一行
        int c = cols - 1;//最后一列

        while( r <= rows - 1 && c >= 0 ){
            if (array[r][c] == target)
                return true;
            else if (array[r][c] > target)//当前值大于目标,说明目标在左侧
                c--;
            else
                r++;
        }

        return false;
    }

【牛客】数组中重复的数字

题目描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

Input:
{2, 3, 1, 0, 2, 5}

Output:
2

思路

  1. 借助一个HashSet来存储,如果出现过则返回。时间复杂度N
public boolean duplicate(int numbers[],int length,int [] duplication) {
        if ( length == 0 || numbers == null ){
            duplication[0] = -1;
            return false;
        }
        HashSet set = new HashSet();

        for (int i = 0 ; i < numbers.length ; i++){
            if (set.contains(numbers[i])){
                duplication[0] = numbers[i];
                return true;
            }
            else
                set.add(numbers[i]);
        }
        duplication[0] = -1;
        return false;
    }
  1. 双重循环,对每个数字,都在后面的数字里查找有没有重复的,时间复杂度N*N
public boolean duplicate(int numbers[],int length,int [] duplication) {
        if ( length == 0 || numbers == null ){
            duplication[0] = -1;
            return false;
        }

        for (int i = 0 ; i < numbers.length ; i++){
            for (int j = i + 1 ; j < numbers.length ; j++){
                if(numbers[i] == numbers[j]){
                    duplication[0] = numbers[i];
                    return true;
                }
            }
        }
        duplication[0] = -1;
        return false;
    }
  1. 先排序,检测第i个数字和第i+1个数字有没有重复,时间复杂度N*logN
public boolean duplicate(int numbers[],int length,int [] duplication) {
        if ( length == 0 || numbers == null ){
            duplication[0] = -1;
            return false;
        }
        Arrays.sort(numbers);
        for (int i = 0 ; i < numbers.length - 1 ; i++){
            if(numbers[i] == numbers[i+1]){
                duplication[0] = numbers[i];
                return true;
            }
        }
        duplication[0] = -1;
        return false;
    }
  1. 由于数组值都在区间[1,n-1]之间,可以把值为i的数字放到位置i上。本题要求找出重复的数字,因此在调整的时候,如果i位置上已经有一个和i相等的数字,就知道i值重复了。(来源

    以 (2, 3, 1, 0, 2, 5) 为例,遍历到位置 4 时,该位置上的数为 2,但是第 2 个位置上已经有一个 2 的值了,因此可以知道 2 重复:

public boolean duplicate(int numbers[],int length,int [] duplication) {
        if ( length == 0 || numbers == null ){
            duplication[0] = -1;
            return false;
        }
        Arrays.sort(numbers);
        for (int i = 0 ; i < numbers.length - 1 ; i++){
            while( numbers[i] != i){
                if (numbers[i] == numbers[numbers[i]]){
                    duplication[0] = numbers[i];
                    return true;
                }
                swap(numbers,i,numbers[i]);
            }
        }
        duplication[0] = -1;
        return false;
    }

    private void swap(int[] nums, int i , int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

【牛客】构建乘积数组

题目描述

给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]A[i-1]A[i+1]A[n-1]。不能使用除法。(注意:规定B[0] = A[1] A[2] A[n-1],B[n-1] = A[0] A[1] A[n-2];)

题目分析

给定的条件就是数组B[i] 的值等于数组A除A[i]之外的乘积,可以用下述表格表示(图源

不过这样看可能不太好理解,看cyc2018大佬博客上的图比较好理解一些:

对每个B[i],都先算出A[0]乘到A[i-1],再算A[n]乘到A[i+1],product就代表第i个,用1表示。

public int[] multiply(int[] A) {
        int n = A.length;
        int[] B = new int[n];

        for(int i  = 0, product = 1 ; i < n ; product *= A[i] , i++)
            B[i] = product;
        for(int i = n - 1 , product = 1 ; i >= 0; product *=A[i] , i--)
            B[i] *= product;

        return B;
    }

参考博客

  1. https://cyc2018.github.io/CS-Notes/#/notes/66.%20%E6%9E%84%E5%BB%BA%E4%B9%98%E7%A7%AF%E6%95%B0%E7%BB%84
  2. https://cyc2018.github.io/CS-Notes/#/notes/3.%20%E6%95%B0%E7%BB%84%E4%B8%AD%E9%87%8D%E5%A4%8D%E7%9A%84%E6%95%B0%E5%AD%97
  3. https://cyc2018.github.io/CS-Notes/#/notes/4.%20%E4%BA%8C%E7%BB%B4%E6%95%B0%E7%BB%84%E4%B8%AD%E7%9A%84%E6%9F%A5%E6%89%BE
  4. https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof/solution/mian-shi-ti-66-gou-jian-cheng-ji-shu-zu-biao-ge-fe/
  • 微信
  • 快加我微信吧~
  • QQ
  • 快加我QQ吧~
  • weinxin
Betterts

发表评论 取消回复