01月13, 2021

【Leetcode题解】-只出现一次的数字、多数元素、搜索二维矩阵

今天分享几个leetcode(力扣)有趣的几个题目的题解

alt

1、只出现一次的数字

题目连接:https://leetcode-cn.com/problems/single-number/

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

题解

题意很明确,就是找数组中只出现一次的数字,如果不关心要求(时间复杂度O(n)、空间复杂度O(1)),可能大多数人想到的是维护一个map,key是数组中的数字,value是出现的次数, 之后再遍历这个map;但是如果要考虑满足O(n)时间复杂度和O(1)空间复杂度,你会怎么做呢?

给你3分钟时间考虑

...........................

时间到!!!

正确的解法是利用:异或运算,只用异或的两个性质:a^a=0,a^0=0;

public int singleNumber(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res ^= nums[i];
        }
        return res;
    }

2、多数元素

Leetcode链接:https://leetcode-cn.com/problems/majority-element/

给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

示例 1:
输入:[3,2,3]
输出:3
示例 2:
输入:[2,2,1,1,1,2,2]
输出:2
 `

进阶: 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

题解

这里提供了三种方法

1、普通思路就不多介绍了,大概还是用map记录数字出现的次数;

2、因为出现次数是大于n/2,所以可以先将数组进行排序,第n/2个元素即是结果;

3、采用类似Boyer-Moore 算法,通过一个count记录结果res的出现次数,result初始化可以是数组第一个元素,那么此时count=1,然后从第二个元素开始遍历数组

    1. 如果当前元素等于res,count++
    1. 如果当前元素不等于res,count--

当count==0,说明之前的元素互相抵消了,然后将result值为当前元素,count开始重新计数,当数组遍历完,此时的result便是出现次数最多的数。 举个例子:

比如数组为[3,3,5,4,7,4,3,3,3],count和res的值变化如下:

数 组:3 3 5 4 7 4 3 3 3

count:1 2 1 0 1 0 1 2 3

result:3 3 3 3 7 7 3 3 3

 public int majorityElement(int[] nums) {
        int count = 1;
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {

            if(count==0){
                res=nums[i];
            }

            if (nums[i] == res) {
                count++;
            } else {
                count--;
            }
        }
        return res;
    }

3、搜索二维矩阵

Leetcode链接:https://leetcode-cn.com/problems/search-a-2d-matrix-ii/

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:

每行的元素从左到右升序排列。 每列的元素从上到下升序排列。

示例 1:

alt

输入: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]], target = 5

输出:true

示例 2:

alt

输入: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]], target = 20

输出:false

题解:

这题最简单的解法就是直接无脑遍历矩阵寻找,时间复杂度是O(m*n),当然也可以稍微优化一下,因为这个矩阵从左到右,从上到下都是有序的,自然可以想到使用二分法,但是这里的二分的是二维数组,大体思路就是从数组的左上角开始沿着对角线,每次遍历从当前元素开始的行和列,对于每行和每列都使用二分,直到遍历完,代码如下

然后我画了几个流程图便于理解(绿色箭头的方向是整体遍历的方向,红色箭头是对每行、每列遍历的方向,当然,每行每列是使用二分去遍历的)

下图分别是3x3、3x5、5x3的矩阵对应算法的流程图

alt

private boolean binarySearch(int[][] matrix, int target, int start, boolean vertical) {
        int lo = start;
        int hi = vertical ? matrix[0].length - 1 : matrix.length - 1;

        while (hi >= lo) {
            int mid = (lo + hi) / 2;
            if (vertical) { // searching a column
                if (matrix[start][mid] < target) {
                    lo = mid + 1;
                } else if (matrix[start][mid] > target) {
                    hi = mid - 1;
                } else {
                    return true;
                }
            } else { // searching a row
                if (matrix[mid][start] < target) {
                    lo = mid + 1;
                } else if (matrix[mid][start] > target) {
                    hi = mid - 1;
                } else {
                    return true;
                }
            }
        }

        return false;
    }

    public boolean searchMatrixBin(int[][] matrix, int target) {
        // an empty matrix obviously does not contain `target`
        if (matrix == null || matrix.length == 0) {
            return false;
        }

        // iterate over matrix diagonals
        int shorterDim = Math.min(matrix.length, matrix[0].length);
        for (int i = 0; i < shorterDim; i++) {
            boolean verticalFound = binarySearch(matrix, target, i, true);
            boolean horizontalFound = binarySearch(matrix, target, i, false);
            if (verticalFound || horizontalFound) {
                return true;
            }
        }

        return false;
    }

这个二分的时间复杂度据说是O(lgn!)

除了上述二分算法,还有一个更为巧妙的算法,他的时间复杂度可以达到O(m+n),一起来了解下吧,思路是从矩阵的左下角开始搜索

  • 1、如果当前值比target大,往右走
  • 2、如果当前值比target小,往上走 其实这个算法也是巧妙地利用了矩阵有序的特性,接下来同样画一个流程图便于大家理解 alt

看代码:

public boolean searchMatrix(int[][] matrix, int target) {
        int x = matrix.length - 1, y = 0;
        while (x >= 0 && y < matrix[0].length) {

            if (target == matrix[x][y]) {
                return true;
            }
            if (target > matrix[x][y]) {
                y++;
            } else {
                x--;
            }
        }
        return false;
    }

比如,target是12,以上是算法从左下角(18)开始遍历的过程,不难看出这个算法的时间复杂度最坏情况下是O(m+n),是不是很巧妙。

总结

以上就是Leetcode3个小题目的题解,都是一些比较有意思的算法,如果你还想了解一些奇技淫巧,不妨去leetcode逛一逛

如果你觉得这篇文章不错,分享给你的小伙伴,一起学习吧~~

个人公众号,目前处于试运营阶段

跪求各位有志之士关注

alt

本文链接:http://blog.keepting.cn/blog//post/leetcode_0113.html

-- EOF --

Comments