LeetCode 中等题解（2）

31 下一个排列

Question

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。

1,2,3 → 1,3,2

3,2,1 → 1,2,3

1,1,5 → 1,5,1

Answer

#

# @lc app=leetcode.cn id=31 lang=python3

#

# [31] 下一个排列

#

# @lc code=start

class Solution:

    def nextPermutation(self, nums: List[int]) -> None:

        """

        Do not return anything, modify nums in-place instead.

        """

        for i in range(len(nums)-1, 0, -1):

            if nums[i] > nums[i-1]:

                res_nums = nums[i:]

                res_nums.sort()

                nums[i:] = res_nums

                for j in range(i, len(nums)):

                    if nums[j] > nums[i-1]:

                        nums[j], nums[i-1] = nums[i-1], nums[j]

                        break

                return

        nums.sort()

# @lc code=end

PS：设计思路：

1.从数组右侧向左开始遍历，找是否存在nums[i]>nums[i-1]的情况，

2.如果不存在这种nums[i]>nums[i-1]情况，for循环会遍历到i==0（也就是没有下一个排列），此时按题意排成有序Arrays.sort()

3.如果存在，则将从下标i到nums.length()的部分排序，然后在排过序的这部分中遍历找到第一个大于nums[i-1]的数，并与nums[i-1]交换位置

33 搜索旋转排序数组

Question

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0

输出: 4

示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3

输出: -1

Answer

#

# @lc app=leetcode.cn id=33 lang=python3

#

# [33] 搜索旋转排序数组

#

# @lc code=start

class Solution:

    def search(self, nums: List[int], target: int) -> int:

        def find_rotate_index(left, right):

            if nums[left] < nums[right]:

                return 0

            while left <= right:

                pivot = (left + right) // 2

                if nums[pivot] > nums[pivot + 1]:

                    return pivot + 1

                else:

                    if nums[pivot] < nums[left]:

                        right = pivot - 1

                    else:

                        left = pivot + 1

        def search(left, right):

            """

            Binary search

            """

            while left <= right:

                pivot = (left + right) // 2

                if nums[pivot] == target:

                    return pivot

                else:

                    if target < nums[pivot]:

                        right = pivot - 1

                    else:

                        left = pivot + 1

            return -1

        n = len(nums)

        if n == 0:

            return -1

        if n == 1:

            return 0 if nums[0] == target else -1 

        rotate_index = find_rotate_index(0, n - 1)

        # if target is the smallest element

        if nums[rotate_index] == target:

            return rotate_index

        # if array is not rotated, search in the entire array

        if rotate_index == 0:

            return search(0, n - 1)

        if target < nums[0]:

            # search on the right side

            return search(rotate_index, n - 1)

        # search on the left side

        return search(0, rotate_index)

# @lc code=end

238 除自身以外数组的乘积

Question

给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例:

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

输出: [24,12,8,6]

提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。

说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。

进阶：

你可以在常数空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

Answer

#

# @lc app=leetcode.cn id=238 lang=python3

#

# [238] 除自身以外数组的乘积

#

# @lc code=start

class Solution:

    def productExceptSelf(self, nums: List[int]) -> List[int]:

        results = []

        left, right = 1, 1

        for i in range(len(nums)):

            results.append(left)

            left *= nums[i]

        for i in range(len(nums) - 1, -1, -1):

            results[i] = results[i] * right

            right *= nums[i]

        return results

# @lc code=end

PS：相当于是先得到要求解的元素左侧的连续积，然后再求得右侧的连续积，之后再进行相乘即可。

287 寻找重复数

Question

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:

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

输出: 2

示例 2:

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

输出: 3

说明：

不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。

Answer

#

# @lc app=leetcode.cn id=287 lang=python3

#

# [287] 寻找重复数

#

# @lc code=start

class Solution:

    def findDuplicate(self, nums: List[int]) -> int:

        left = 1

        right = len(nums) - 1

        while (left < right):

            mid = (left + right) // 2

            count = 0

            for num in nums:

                if (num <= mid):

                    count += 1

            if (count <= mid):

                left = mid + 1

            else:

                right = mid

        return left

# @lc code=end

巴特西

LeetCode 中等题解（2）

31 下一个排列

Question

Answer

33 搜索旋转排序数组

Question

Answer

238 除自身以外数组的乘积

Question

Answer

287 寻找重复数

Question

Answer

最新文章

热门文章