剑指OFFER练习记录(一. 数组部分)

这是自己刷题的笔记, 有Java和Python的实现, 尽量每一题都挑选典型的方法进行记录. 题目的分类是按照牛客平台分类的.

题目连接

二维数组中的查找

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

思路(二分查找):

• 我们把初始坐标定位在右上角[i, j], 根据排序特性, 此时指向的数比左边的数大, 比下面的数小.
• 查找目标数记录为target, 如果target < arr[i, j], 则target若在arr中存在, 只可能在[i, j]位置的坐标的左边; 如果target > arr[i, j], 则target只可能在[i, j]位置的下边.

public class Solution {
    public boolean Find(int target, int[][] array) {
        if (array.length == 0 || array[0].length == 0) {
            return false;
        }

        int endX = array.length - 1;
        int endY = array[0].length - 1;
        int x = 0;
        int y = endY;

        while (x <= endX && y >= 0) {
            if (target == array[x][y]) {
                return true;
            } else if (target < array[x][y]) {
                y--;
            } else if (target > array[x][y]) {
                x++;
            }
        }
        return false;
    }
}

class Solution:
    def Find(self, target, array):
        if array is None or array[0] is None:
            return False

        end_x, end_y = len(array) - 1, len(array[0]) - 1
        x, y = 0, end_y

        while x <= end_x and y >= 0:
            if target == array[x][y]:
                return True
            elif target < array[x][y]:
                y -= 1
            else:
                x += 1
        return False

数组中重复的数字

题目:
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

思路(哈希):
利用哈希集合收集数组中出现过的数, 在遍历数组过程中对从哈希表进行检查即可. 这种方法的额外空间复杂度为O(n)

import java.util.HashSet;

public class Solution {
    public boolean duplicate(int numbers[], int length, int[] duplication) {
        if (length == 0) return false;
        HashSet<Integer> set = new HashSet<>();
        for (int i : numbers) {
            if (set.contains(i)) {
                duplication[0] = i;
                return true;
            } else {
                set.add(i);
            }
        }
        duplication[0] = -1;
        return false;
    }
}

class Solution:
    def duplicate(self, numbers, duplication):
        duplication[0] = -1
        if len(numbers) == 0:
            return False
        my_set = set()
        for i in numbers:
            if i in my_set:
                duplication[0] = i
                return True
            else:
                my_set.add(i)
        return False

构建乘积数组

题目: 给定一个数组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];）

思路(两个数组存放当前位置以前的累乘和当前位置以后的累乘积):

• 从尾遍历数组, 对于每个位置i, 都记录该数之后的数的累乘(不包括i位置的数)
• 从头遍历数组, 对于每个位置i, 都记录包括该数之前的数的累乘(不包括i位置的数)
• 把两个数组对应位置的数乘起来

class Solution {
    public int[] multiply(int[] A) {
        if (A.length == 0) return new int[0];

        int[] tmp = new int[A.length];
        int[] res = new int[A.length];
        tmp[A.length - 1] = 1;

        for (int i = A.length - 2; i >= 0; i--) {
            tmp[i] = A[i + 1] * tmp[i + 1];
        }

        int cur = 1;
        for (int i = 1; i < A.length; i++) {
            // 只需要一个遍历记录累乘的数
            cur *= A[i - 1];
            res[i] = cur * tmp[i];
        }
        res[0] = tmp[0];
        return res;
    }
}

class Solution:
    def multiply(self, A):
        tmp = [1 for i in range(len(A))]
        res = []
        for i in range(len(A) - 2, -1, -1):
            tmp[i] = A[i + 1] * tmp[i + 1]

        cur = 1
        res.append(tmp[0])
        for i in range(1, len(A), 1):
            cur *= A[i - 1]
            res.append(cur * tmp[i])
        return res