头像

瑞絮


访客:1427

离线:2个月前



瑞絮
2019-03-21 06:31

题目描述

在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。

请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

样例

输入数组:

[
  [1,2,8,9],
  [2,4,9,12],
  [4,7,10,13],
  [6,8,11,15]
]

如果输入查找数值为7,则返回true,

如果输入查找数值为5,则返回false。

算法

(扫描法) $O(m+n)$

主要就是发现这个二维数组的规律:每行中最右侧数最大,每列中最下侧数最大。

从最右上方开始进行扫描,
若当前值array[i][j]正好等于target,返回True
否则若当前值array[i][j]小于target,则说明当前位置正左侧的数都小于target,行号i加1;
否则若当前值array[i][j]大于target,则说明当前位置正下侧的数都大于target,列号j减1。
直至遍历到最左下方仍没有找到与target相同的值,返回False

时间复杂度分析:最差的情况是二维数组(m*n)中没有要找的值,走了m+n步,时间复杂度$O(m+n)$。

C 代码

bool searchArray(int** array, int arrayRowSize, int arrayColSize, int target) {
    int i = 0;
    int j = arrayColSize - 1;
    while(i < arrayRowSize && j >= 0)
    {
        if(array[i][j] == target)
            return true;
        else if(array[i][j] < target)
            i++;
        else
            j--;
    }
    return false;
}

Python3 代码

class Solution(object):
    def searchArray(self, array, target):
        """
        :type array: List[List[int]]
        :type target: int
        :rtype: bool
        """
        # 如果数组为空
        if not array or not array[0]: return False
        # 获取二维数组的行数和列数
        rowLen, colLen = len(array), len(array[0])
        # 0赋给i,colLen-1赋给j
        i, j = 0, colLen - 1
        while i < rowLen and j >= 0:
            if array[i][j] == target:
                return True
            elif array[i][j] < target:
                i += 1
            else:
                j -= 1
        return False



瑞絮
2019-03-20 01:32

题目描述

给定一个长度为 n 的整数数组 nums,数组中所有的数字都在 0∼n−1 的范围内。

数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。

请找出数组中任意一个重复的数字。

注意:如果某些数字不在 0∼n−1 的范围内,或数组中不包含重复数字,则返回 -1;

样例

给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。

算法

(数组遍历) $O(n)$

一个简单的思路,就是把nums中所有数字的出现次数都记录下来,返回第一个次数大于0的即可。
首先,我们需要一个列表li用来存放数字出现次数,由题得数字在0~n-1之间,因此li的长度与nums相等,li[i]即表示数字i在nums中出现的次数;
然后,遍历数组nums,判断数字在0~n-1范围内,不满足的话不符合题目要求,返回-1,满足的话再累计数字出现的次数;
最后,遍历完数组nums后,输出li列表中任意一个li[i]大于0的下标i
OVER!!!

时间复杂度分析:整个下来,我们的操作有:初始化一个列表、遍历一个长度为n的数组、在长度为n的列表中查找大于0的值,因此最坏的情况也是2n,同数量级$O(n)$

Python3 代码

class Solution(object):
    def duplicateInArray(self, nums):
        """
        :type nums: List[int]
        :rtype int
        """
        # 获取列表的长度
        length = len(nums);
        # 初始化一个长度为length的列表
        li = [0]*length;
        # 遍历列表中的值,i为列表中的元素值
        for i in nums:
            if i < 0 or i > length - 1:
                return -1
            li[i] += 1;
        # i为0~length-1
        for i in range(length):
            if li[i] > 1:
                return i
        return -1