Array Introduction

本文蒐集

• LeetCode 485
• LeetCode 1295
• LeetCode 977

LeetCode 485: Max Consecutive Ones

Given a binary array, find the maximum number of consecutive 1s in this array.

Example 1:

Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.
    The maximum number of consecutive 1s is 3.

Note:

• The input array will only contain 0 and 1.
• The length of input array is a positive integer and will not exceed 10,000

我的解答

q485_loop.pyview raw
class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        count = 0
        m = 0
        for i in range(len(nums)):
            if nums[i] == 1:
                count += 1
            else:
                if count > m:
                    m = count
                count = 0
        return max(m, count)

• Time Complexity: O(n)
• Auxiliary Space: O(1)

利用 itertools.groupby

q485_itertools.groupby.pyview raw
class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        if 1 not in nums: return 0
        groups = [(key, len(list(group))) for key, group in itertools.groupby(nums) if key == 1] # [(1, 2), (0, 1), (1, 3)]
        return max(groups, key=lambda s: s[1])[1]

不建議使用內部函式，這邊只是提供簡潔寫法

LeetCode 1295: Find Numbers with Even Number of Digits

Given an array nums of integers, return how many of them contain an even number of digits.

Example 1:

Input: nums = [12,345,2,6,7896]
Output: 2
Explanation: 
12 contains 2 digits (even number of digits). 
345 contains 3 digits (odd number of digits). 
2 contains 1 digit (odd number of digits). 
6 contains 1 digit (odd number of digits). 
7896 contains 4 digits (even number of digits). 
Therefore only 12 and 7896 contain an even number of digits.

Example 2:

Input: nums = [555,901,482,1771]
Output: 1 
Explanation: 
Only 1771 contains an even number of digits.

Constraints:

• 1 <= nums.length <= 500
• 1 <= nums[i] <= 10^5

我的解答

q1295.pyview raw
class Solution:
    def findNumbers(self, nums: List[int]) -> int:
        count = 0
        for i in nums:
            if len(str(i)) % 2 == 0:
                count += 1
        return count

• Time Complexity: O(N * log(max(nums[i])))
• Space Complexity: O(1)

我竟然沒想到 len(str())

q1295_str.pyview raw
class Solution:
    def findNumbers(self, nums: List[int]) -> int:
        count = 0
        for i in nums:
            if len(str(i)) % 2 == 0:
                count += 1
        return count

不建議

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 1:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

Example 2:

Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Constraints:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• 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?

我的解答

q977.pyview raw
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

• Time complexity: O(n)
• Auxiliary Space: O(n)

利用 MergeSort 的概念

q977_MergeSort.pyview raw
# Python3 program to Sort square of the numbers of the array

# function to sort array after doing squares of elements
def sortSquares(arr, n):
	
    # first dived array into part negative and positive
    K = 0
    for K in range(n):
	    if (arr[K] >= 0 ):
       	    break
	
    # Now do the same process that we learn
    # in merge sort to merge to two sorted array
    # here both two half are sorted and we traverse
    # first half in reverse meaner because
    # first half contain negative element
    i = K - 1 # Initial index of first half
    j = K # Initial index of second half
    ind = 0 # Initial index of temp array
	
    # store sorted array
    temp = [0]*n
    while (i >= 0 and j < n):	
	    if (arr[i] * arr[i] < arr[j] * arr[j]):
       	    temp[ind] = arr[i] * arr[i]
	        i -= 1
	    else:
	        temp[ind] = arr[j] * arr[j]
	        j += 1	
	    ind += 1
	
    ''' Copy the remaining elements of first half '''
    while (i >= 0):	
	    temp[ind] = arr[i] * arr[i]
	    i -= 1
	    ind += 1
		
    ''' Copy the remaining elements of second half '''
    while (j < n):
	    temp[ind] = arr[j] * arr[j]
	    j += 1
	    ind += 1
		
    # copy 'temp' array into original array
    for i in range(n):
	    arr[i] = temp[i]

# Driver code
arr = [-6, -3, -1, 2, 4, 5 ]
n = len(arr)

print("Before sort ")
for i in range(n):
    print(arr[i], end =" " )
	
sortSquares(arr, n)
print("\nAfter Sort ")
for i in range(n):
    print(arr[i], end =" " )

• Time complexity: O(n)
• space complexity: O(n)