Array Conclusion

本文蒐集

• LeetCode 1051
• LeetCode 414
• LeetCode 448
• LeetCode 977

LeetCode 1051: Height Checker

Students are asked to stand in non-decreasing order of heights for an annual photo.

Return the minimum number of students that must move in order for all students to be standing in non-decreasing order of height.

Notice that when a group of students is selected they can reorder in any possible way between themselves and the non selected students remain on their seats.

Example:

Constraints:

• 1 <= heights.length <= 100
• 1 <= heights[i] <= 100

我的解答

class Solution:
    def heightChecker(self, heights: List[int]) -> int:
        def quicksort(heights: List[int], left, right) -> None:
            if left >= right:
                return
            i = left
            j = right
            pivot = heights[left]

            while i != j:
                while heights[j] > pivot and i < j:
                    j -= 1
                while heights[i] <= pivot and i < j:
                    i += 1
                if i < j:
                    heights[i], heights[j] = heights[j], heights[i]
            heights[left], heights[i] = heights[i], heights[left]
            quicksort(heights, left, i-1)
            quicksort(heights, i+1, right)
        
        temp = [0] * len(heights)
        temp[:] = heights[:]
        quicksort(heights, 0, len(heights)-1)
        count = 0
        for i in range(len(heights)):
            if temp[i] != heights[i]:
                count += 1
        return count

LeetCode 414: Third Maximum Number

Given integer array nums, return the third maximum number in this array. If the third maximum does not exist, return the maximum number.

Example:

Constraints:

• 1 <= nums.length <= \(10^4\)
• \(-2^31\) <= nums[i] <= \(2^31\) - 1

Follow up: Can you find an O(n) solution?

我的解答

import math
class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        temp = []
        for _ in range(3):
            m = -math.inf
            if _ == 0:
                for i in nums:
                    if i > m:
                        m = i
            else:
                for i in nums:
                    if temp[-1] > i > m:
                        m = i
            if m != -math.inf:
                temp.append(m)
        if len(temp) == 3:
            return temp[-1]
        else:
            return temp[0]

LeetCode 448: Find All Numbers Disappeared in an Array

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

Example:

Constraints:

• n == nums.length
• 1 <= n <= \(10^5\)
• 1 <= nums[i] <= n

Follow up: Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

我的解答

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        for i in nums:
            i = abs(i)
            nums[i-1] = -abs(nums[i-1])
        return [i+1 for i, value in enumerate(nums) if value > 0]

LeetCode 977: Squares of a Sorted Array

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example:

Constraints:

• 1 <= nums.length <= \(10^4\)
• \(-10^4\) <= nums[i] <= \(10^4\)
• nums is sorted in non-decreasing order.

Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?

我的解答

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        i = 0
        j = len(nums) - 1
        k = 0
        ans = [0] * len(nums)
        for _ in range(len(nums)):
            nums[_] = nums[_] ** 2
        while i <= j:
            if nums[i] > nums[j]:
                ans[k] = nums[i]
                i += 1
            else:
                ans[k] = nums[j]
                j -= 1
            k += 1
        for i in range(len(nums)):
            nums[i] = ans[len(nums)-1-i]
        return nums