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：

1
2
3
4
5
6
7
8
输入：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：

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

示例 3：

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

提示：

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

代码

  • 时间复杂度O(Nlogn)
  • 空间复杂度O(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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]

img

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

思路一

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

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

代码一

  • 时间复杂度O(N)
  • 空间复杂度O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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：

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

示例 2：

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

示例 3：

1
2
输入：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就可以了。

如图所示：

img

img

代码

  • 时间复杂度O(N)
  • 空间复杂度O(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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:

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

示例 2:

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

提示:

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

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

思路

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

如动画所示：

移动零

移动零

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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:

1
2
3
4
5
6
输入: 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:

1
2
3
4
5
输入：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)
1
2
3
4
5
6
7
8
9
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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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：

1
2
3
4
5
6
输入：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：

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

示例 3：

1
2
3
4
5
6
输入：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

代码一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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)
1
2
3
4
5
6
7
8
9
10
11
12
13
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：

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

示例 2：

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

示例 3：

1
2
输入：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作为左边界），所以需要对原二分查找进行修改

原二分查找的代码如下

1
2
3
4
5
6
7
8
9
10
11
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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
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]