LeetCodeCampsDay64额外题目

1365. 有多少小于当前数字的数字

https://leetcode.cn/problems/how-many-numbers-are-smaller-than-the-current-number/

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。

换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。

以数组形式返回答案。

示例 1：

输入：nums = [8,1,2,2,3]
输出：[4,0,1,1,3]
解释： 
对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。 
对于 nums[1]=1 不存在比它小的数字。
对于 nums[2]=2 存在一个比它小的数字：（1）。 
对于 nums[3]=2 存在一个比它小的数字：（1）。 
对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。

示例 2：

输入：nums = [6,5,4,8]
输出：[2,1,0,3]

示例 3：

输入：nums = [7,7,7,7]
输出：[0,0,0,0]

提示：

2 <= nums.length <= 500
0 <= nums[i] <= 100

代码

时间复杂度O(Nlogn)
空间复杂度O(N)

class Solution:

    def quickSort(self, arr: list) -> list:
        Larr = len(arr)
        if Larr <= 1:
            return arr
        pivot = arr[0]
        left = [x for x in arr[1:] if x <= pivot]
        right = [x for x in arr[1:] if x > pivot]
        return self.quickSort(left) + [pivot] + self.quickSort(right)

    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        # 先做个排序，排序后的下标数i就是比nums[i]小的个数
        # 使用hash table
        numsSorted = self.quickSort(nums)
        Lnums = len(numsSorted)
        table = dict()
        table[numsSorted[0]] = 0
        for i in range(1, Lnums):
            # 比如1，2，2，3；若遇到相同的两个值，不用进行更新；
            # 或者判断numsSorted[i]是否已经在table里，如果存在，不用进行更新；
            if numsSorted[i] > numsSorted[i - 1]:
                table[numsSorted[i]] = i
        
        # 最后，按原数组的顺序展示结果
        res = [0] * Lnums
        for i in range(0, Lnums):
            res[i] = table[nums[i]]

        return res

941. 有效的山脉数组

https://leetcode.cn/problems/valid-mountain-array/

给定一个整数数组 arr，如果它是有效的山脉数组就返回 true，否则返回 false。

让我们回顾一下，如果 arr 满足下述条件，那么它是一个山脉数组：

arr.length >= 3
在 0 < i < arr.length - 1 条件下，存在 i 使得：
- arr[0] < arr[1] < ... arr[i-1] < arr[i]
- arr[i] > arr[i+1] > ... > arr[arr.length - 1]

示例 1：

输入：arr = [2,1]
输出：false

示例 2：

输入：arr = [3,5,5]
输出：false

示例 3：

输入：arr = [0,3,2,1]
输出：true

提示：

1 <= arr.length <= 104
0 <= arr[i] <= 104

思路一

本题目要经过再次循环判断，先判断是否单调递增；再判断是否单调递减；

先找到假设中的TheMaxIndex递增序列里的最大值，再进行单调递减的判断，最终根据TheMaxIndex是否非头非尾以及index是否遍历完来判断结果

代码一

时间复杂度O(N)
空间复杂度O(1)

class Solution:
    def validMountainArray(self, arr: List[int]) -> bool:
        
        TheTop = -1
        L = len(arr)
        theMaxIndex = 0
        index = 1
        while index < L and arr[theMaxIndex] < arr[index]:
            theMaxIndex = index
            index += 1
        
        theMinIndex = theMaxIndex
        # 此时假设已经找到峰值，后面的数据都必须逐个减少，否则就False
        while index < L and arr[theMinIndex] > arr[index]:
            theMinIndex = index
            index += 1
        
        if index == L and theMaxIndex != 0 and theMaxIndex != L -  1:
            return True
        else:
            return False

思路二

使用二指针，left指针从左向右遍历，判断是否单调递增；right指针从右向左遍历，判断是否单调递减；

若最终两个指针位置相同，并且非头非尾（!=0且!=L-1），说明才符合要求

代码二

时间复杂度O(N)
空间复杂度O(1)

class Solution:
    def validMountainArray(self, arr: List[int]) -> bool:
        # 双指针，左指针从左向右遍历；右指针从右向左遍历，如果最终在峰值相遇
        L = len(arr)
        if L < 3: 
            return False
        
        left = 0
        right = L - 1
        
        while left < L - 1 and arr[left] < arr[left + 1]:
            left += 1
        while right > 0 and arr[right] < arr[right - 1]:
            right -= 1
        
        if left == right and left !=0 and right != L - 1:
            return True
        return False

1207. 独一无二的出现次数

https://leetcode.cn/problems/unique-number-of-occurrences/

给你一个整数数组 arr，如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。

示例 1：

输入：arr = [1,2,2,1,1,3]
输出：true
解释：在该数组中，1 出现了 3 次，2 出现了 2 次，3 只出现了 1 次。没有两个数的出现次数相同。

示例 2：

输入：arr = [1,2]
输出：false

示例 3：

输入：arr = [-3,0,1,-3,1,1,1,-3,10,0]
输出：true

提示：

1 <= arr.length <= 1000
-1000 <= arr[i] <= 1000

思路

回归本题，本题强调了-1000 <= arr[i] <= 1000，那么就可以用数组来做哈希，arr[i]作为哈希表（数组）的下标，那么arr[i]可以是负数，怎么办？负数不能做数组下标。

此时可以定义一个2001大小的数组，例如int count[2001];，统计的时候，将arr[i]统一加1000，这样就可以统计arr[i]的出现频率了。

题目中要求的是是否有相同的频率出现，那么需要再定义一个哈希表（数组）用来记录频率是否重复出现过，bool fre[1001]; 定义布尔类型的就可以了，因为题目中强调1 <= arr.length <= 1000，所以哈希表大小为1000就可以了。

如图所示：

代码

时间复杂度O(N)
空间复杂度O(N)

class Solution:
    def uniqueOccurrences(self, arr: List[int]) -> bool:
        # 使用hashtable
        table = dict()
        L = len(arr)
        for i in range(L):
            table[arr[i]] = table.get(arr[i], 0) + 1
        
        # 方法一
        # table已经记录了每个数字出现次数，可以再建立个set表，把不重复的次数添加进去
        # res = set()
        # for i in table.values():
        #     res.add(i)

        # if len(table) != len(res):
        #     return False
        # return True
				
				
				# 方法二
        # table已经记录了每个数字出现次数，对次数按顺序排序，如果出现相同的两个值则False
        Ltable = len(table)
        valuesList = sorted(table.values())
        for i in range(1, Ltable):
            if valuesList[i - 1] == valuesList[i]:
                return False
        return True

283. 移动零

https://leetcode.cn/problems/move-zeroes/

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

提示:

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

**进阶：**你能尽量减少完成的操作次数吗？

思路

使用双指针，slow指向可以放数据的下标，fast用来遍历，如果fast遇到非0则将nums[fast]赋值到nums[slow]；最后将nums[slow:]这个范围内的值赋值为0

如动画所示：

代码

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        slow = 0
        fast = 0
        L = len(nums)
        while fast < L:
            if nums[fast] != 0:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        
        for i in range(slow, L):
            nums[i] = 0

189. 轮转数组

https://leetcode.cn/problems/rotate-array/

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

进阶：

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的原地算法解决这个问题吗？

数据复制思路

我们遍历原数组，将原数组下标为 i 的元素放至新数组下标为 (i+k)modn 的位置，最后将新数组拷贝至原数组即可。

数据复制代码

时间复杂度O(N)
空间复杂度O(N)

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        L = len(nums)
        k %= L
        new_nums = [0] * L
        for i in range(L):
            new_nums[ (i + k) % L ] = nums[i]
        for i in range(L):
            nums[i] = new_nums[i]

数组翻转思路

该方法基于如下的事实：当我们将数组的元素向右移动 k 次后，尾部 k mod n 个元素会移动至数组头部，其余元素向后移动 k mod n 个位置。

该方法为数组的翻转：我们可以先将所有元素翻转，这样尾部的 k mod n 个元素就被移至数组头部，然后我们再翻转 [0,k mod n−1] 区间的元素和 [k mod n,n−1] 区间的元素即能得到最后的答案。

我们以 n=7，k=3 为例进行如下展示：

操作	结果
原始数组	1 2 3 4 5 6 7
翻转所有元素	7 6 5 4 3 2 1
翻转 [0,k mod n−1] 区间的元素	5 6 7 4 3 2 1
翻转 [k mod n,n−1] 区间的元素	5 6 7 1 2 3 4

下面为了省事，直接将k = k % n

数组翻转代码

时间复杂度O(N)
空间复杂度O(1)

class Solution:

    def swap(self, nums: list):
        left = 0
        L = len(nums)
        right = L - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1
        return nums

    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 整体反转、前k反转、后n-k反转
        L = len(nums)
        nums = self.swap(nums)
        k = k % L
        nums[:k] = self.swap(nums[:k])
        nums[k:] = self.swap(nums[k:])

        # 使用python自带（但实际使用了O(N)空间
        #nums[:] = nums[-k:] + nums[:-k]

724. 寻找数组的中心下标

https://leetcode.cn/problems/find-pivot-index/

给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

示例 1：

输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。

示例 2：

输入：nums = [1, 2, 3]
输出：-1
解释：
数组中不存在满足此条件的中心下标。

示例 3：

输入：nums = [2, 1, -1]
输出：0
解释：
中心下标是 0 。
左侧数之和 sum = 0 ，（下标 0 左侧不存在元素），
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。

提示：

1 <= nums.length <= 104
-1000 <= nums[i] <= 1000

思路一

使用两个数组分别从左向右、从右向左计算累加值

随后，对两个数组判断是否存在一个同一下标i的相同值

中心下标位置的数字不参加运算

双指针，left从左向右；right从右向左遍历；同时求和

0, 1, 8, 11, 17, 22, 28

22, 21, 14, 17, 11, 6, 0

如果遇到下标位置一致且两个数组值一致，则返回这个下标

0, 2, 3, 2

2, 0, -1, 0

代码一

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        

        L = len(nums)
        sumFromLeft = [0] * (L + 1)
        sumFromRight = [0] * (L + 1)

        for i in range(L):
            sumFromLeft[i + 1] += nums[i] + sumFromLeft[i]
            sumFromRight[L - 1 - i] += nums[L - 1 - i] + sumFromRight[L - i]
        
        left = 0
        right = L

        for i in range(1, L + 1):
            if sumFromLeft[i] == sumFromRight[i - 1]:
                return i - 1
        
        return -1

思路二

先求出数组整体和，再从左向右遍历，实时地计算sumOfLeft以及sumOfRight的和，判断是否相等即可

代码二

时间复杂度O(N)
空间复杂度O(N)

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        sumOfAll = sum(nums)
        L = len(nums)
        sumOfLeft = 0
        sumOfRight = 0
        for i in range(L):
            sumOfRight = sumOfAll - sumOfLeft
            sumOfLeft += nums[i]
            if sumOfLeft == sumOfRight:
                return i
        
        return -1

34. 在排序数组中查找元素的第一个和最后一个位置

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

思路

本题基本指定使用二分查找，基础的二分查找中，仅能查到指定的target，但本题目要求查这个target的区间范围。

所以，本题目需要划分成查找target的左、右区间边界（即，例如5,7,7,8,8,10，需要找到第一个10作为右边界，以及第二个7作为左边界），所以需要对原二分查找进行修改

原二分查找的代码如下

L = len(nums)
left = 0
right = L - 1
while left <= right:
    mid = (left + right) // 2
    if nums[mid] < target:
        left = mid + 1
    elif nums[mid] > target:
        right = mid - 1
    else:
        return mid

如果要查左边界leftBorder，应该当nums[mid] >= target时，将mid - 1赋值给leftBorder

比如，5,7,7,8,8,10，当left为3，right为5，mid为4，即nums[mid]为第二个8时，此时满足nums[mid]>=target，则leftBorder就是mid - 1 = 3

代码

时间复杂度O(logN)
空间复杂度O(N)

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # 如果指定logn时间复杂度, 使用递归的方法或二分法
        if L == 0:
            return [-1, -1]
				# 5,7,7,8,8,10
        # 这里leftBorder找的应该是第二个7的下标
        def findLeftBorder(nums, target):
            L = len(nums)
            left = 0
            right = L - 1
            leftBorder = -2
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
                    leftBorder = right
            return leftBorder
        
        # 5,7,7,8,8,10
        # 这里的rightBorder应该找第一个10的下标
        def findRightBorder(nums, target):
            L = len(nums)
            left = 0
            right = L - 1
            rightBorder = -2
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] <= target:
                    left = mid + 1
                    rightBorder = left
                else: 
                    right = mid - 1
            return rightBorder
        

        leftBorder = findLeftBorder(nums, target)
        rightBorder = findRightBorder(nums, target)
        # print(leftBorder, rightBorder)
        if leftBorder == -2 or rightBorder == -2:
            return [-1, -1]
        elif leftBorder < rightBorder - 1:
          	# 
            return [leftBorder + 1, rightBorder - 1]
        return [-1, -1]

1365. 有多少小于当前数字的数字

代码

941. 有效的山脉数组

思路一

代码一

思路二

代码二

1207. 独一无二的出现次数

思路

代码

283. 移动零

思路

代码

189. 轮转数组

数据复制思路

数据复制代码

数组翻转思路

数组翻转代码

724. 寻找数组的中心下标

思路一

代码一

思路二

代码二

34. 在排序数组中查找元素的第一个和最后一个位置

思路

代码

相关推荐