8. 数组操作

Q41. 缺失的第一个正数 HARD

给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。 示例 1: 输入: [1,2,0] 输出: 3 示例 2: 输入: [3,4,-1,1] 输出: 2 示例 3: 输入: [7,8,9,11,12] 输出: 1 提示： 你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。 通过次数65,179 | 提交次数164,825

class Solution:
    def firstMissingPositive(self,nums: List[int]) -> int:
        '''1.置换法'''
        n = len(nums)
        for i in range(n):
            while 1<=nums[i]<=n and nums[nums[i]-1]!=nums[i]:
                nums[nums[i]-1],nums[i] = nums[i],nums[nums[i]-1]
        for i in range(n):
            if nums[i]!=i+1:
                return i+1
        return n+1
        '''2. hash'''

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int& num: nums) {
            if (num <= 0) {
                num = n + 1;
            }
        }
        for (int i = 0; i < n; ++i) {
            int num = abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -abs(nums[num - 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }
};

Q54. 螺旋矩阵 MEDIUM

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。 示例 1: 输入: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] 输出: [1,2,3,6,9,8,7,4,5] 通过次数63,643 | 提交次数157,058

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res = []
        if matrix:
            m,n = len(matrix),len(matrix[0])
            i,j =0,0
            fi,fj =0,1
            for index in range(m*n):
                res.append(matrix[i][j])
                matrix[i][j] =''
                if matrix[(i+fi)%m][(j+fj)%n] == '':
                    fi,fj = fj, -fi
                i+=fi
                j+=fj
        return res

Q59. 螺旋矩阵 II MEDIUM

给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。 示例: 输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] 通过次数36,382 | 提交次数46,954

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        res =[[0 for _ in range(n)] for _ in range(n)]
        i,j =0,0
        fi,fj =0,1
        for index in range(1,n*n+1):
            res[i][j] += index
            if res[(i+fi)%n][(j+fj)%n] !=0:
                fi,fj = fj,-fi 
            i +=fi
            j+=fj
        return res

Q73. 矩阵置零 MEDIUM

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。 示例 1: 输入: [ [1,1,1], [1,0,1], [1,1,1] ] 输出: [ [1,0,1], [0,0,0], [1,0,1] ] 通过次数42,084 | 提交次数75,840

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m, n = len(matrix), len(matrix[0])
        fr,fc = 0,0
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0
                    if i == 0 : fr += 1
                    if j == 0 : fc += 1
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0
        if fr:
            for j in range(n):
                matrix[0][j] = 0
        if fc:
            for i in range(m):
                matrix[i][0] = 0

Q945. 使数组唯一的最小增量 MEDIUM

给定整数数组 A，每次 move 操作将会选择任意 A[i]，并将其递增 1。 返回使 A 中的每个值都是唯一的最少操作次数。 示例 1: 输入：[1,2,2] 输出：1 解释：经过一次 move 操作，数组将变为 [1, 2, 3]。 示例 2: 输入：[3,2,1,2,1,7] 输出：6 解释：经过 6 次 move 操作，数组将变为 [3, 4, 1, 2, 5, 7]。 可以看出 5 次或 5 次以下的 move 操作是不能让数组的每个值唯一的。 提示： 0 <= A.length <= 40000 0 <= A[i] < 40000 通过次数28,275 | 提交次数59,060

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        '''1 排序O(NlogN)'''
        A.sort()
        move = 0
        for i in range(1,len(A)):
            if A[i] <= A[i-1]:
                temp = A[i]
                A[i] = A[i-1] + 1
                move+=A[i] - temp
        return move

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        '''计数 O(n)'''
        if A == []:
            return 0
        count = [0]*40001
        move = 0
        for i in A:
            count[i] +=1
        xam = max(A)
        for i in range(xam+1):
            if count[i]>1:
                count[i+1]+=count[i]-1
                move += count[i] -1 
        move+= (count[xam+1]-1)*(count[xam+1]-1+1) //2   # (a0+an)*(n-0)//2
        return move