In-Place Operations
本文蒐集
LeetCode 1299: Replace Elements with Greatest Element on Right Side
Given an array arr, replace every element in that array with the greatest element among the elements to its right, and replace the last element with -1.
After doing so, return the array.
Example 1:
Input: arr = [17,18,5,4,6,1]
Output: [18,6,6,6,1,-1]
Explanation:
- index 0 --> the greatest element to the right of index 0 is index 1 (18).
- index 1 --> the greatest element to the right of index 1 is index 4 (6).
- index 2 --> the greatest element to the right of index 2 is index 4 (6).
- index 3 --> the greatest element to the right of index 3 is index 4 (6).
- index 4 --> the greatest element to the right of index 4 is index 5 (1).
- index 5 --> there are no elements to the right of index 5, so we put -1.Input: arr = [400]
Output: [-1]
Explanation: There are no elements to the right of index 0.Constraints:
- 1 <= arr.length <= \(10^4\)
- 1 <= arr[i] <= \(10^5\)
我的解答
class Solution:
def replaceElements(self, arr: List[int]) -> List[int]:
j = len(arr)-2
max = arr[len(arr)-1]
while j >= 0:
if arr[j] > max:
arr[j], max = max, arr[j]
else:
arr[j] = max
j -= 1
arr[len(arr)-1] = -1
return arrTime: O(n) Space: O(1)
LeetCode 26: Remove Duplicates from Sorted Array
Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. Clarification:
Confused why the returned value is an integer but your answer is an array?
Note that the input array is passed in by reference, which means a modification to the input array will be known to the caller as well.
Internally you can think of this:
// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);
// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}Input: nums = [1,1,2]
Output: 2, nums = [1,2]
Explanation: Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the returned length.Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4]
Explanation: Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively. It doesn't matter what values are set beyond the returned length.0 <= nums.length <= 3 * 104-104 <= nums[i] <= 104numsis sorted in ascending order.
我的解法
q26.pyview rawimport math class Solution: def removeDuplicates(self, nums: List[int]) -> int: temp = -math.inf count = 0 for i in range(len(nums)): if nums[i] > temp: temp = nums[i] nums[count] = temp count += 1 return count
解答
q26解.pyview rawclass Solution: def removeDuplicates(self, nums: List[int]) -> int: if len(nums) == 0: return 0 i = 0 for j in range(1, len(nums)): if nums[j] != nums[i]: i += 1 nums[i] = nums[j] return i+1
LeetCode 283: Move Zeroes
Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.
Example 1:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]Input: nums = [0]
Output: [0]Constraints:
- 1 <= nums.length <= \(10^4\)
- \(-2^31\) <= nums[i] <= \(2^31\) - 1
Follow up: Could you minimize the total number of operations done?
我的解答
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
i = 0
count = 0
while i < len(nums):
if nums[i] != 0:
nums[count] = nums[i]
count += 1
i += 1
while count < len(nums):
nums[count] = 0
count += 1Time: O(n) Space: O(1)
LeetCode 905: Sort Array By Parity
Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.
You may return any answer array that satisfies this condition.
Example 1:
Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.Note:
1 <= A.length <= 50000 <= A[i] <= 5000
我的解答
class Solution:
def sortArrayByParity(self, A: List[int]) -> List[int]:
i = 0
j = len(A)-1
while i < j:
while A[i] % 2 != 1 and i < j:
i += 1
while A[j] % 2 != 0 and i < j:
j -= 1
A[i], A[j] = A[j], A[i]
return ATime: O(n) Space: O(1)
LeetCode 27: Remove Element
Given an array nums and a value val, remove all instances of that value in-place and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.
Clarification:
Confused why the returned value is an integer but your answer is an array?
Note that the input array is passed in by reference, which means a modification to the input array will be known to the caller as well.
Internally you can think of this:
// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);
// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2]
Explanation: Your function should return length = 2, with the first two elements of nums being 2.
It doesn't matter what you leave beyond the returned length. For example if you return 2 with nums = [2,2,3,3] or nums = [2,2,0,0], your answer will be accepted.Example 2:
Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3]
Explanation: Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4. Note that the order of those five elements can be arbitrary. It doesn't matter what values are set beyond the returned length.0 <= nums.length <= 1000 <= nums[i] <= 500 <= val <= 100
我的解法: 利用 BubbleSort
q27_BubbleSort.pyview rawclass Solution: def removeElement(self, nums: List[int], val: int) -> int: l = len(nums) count = 0 for i in range(l-1): swapped = False for j in range(l-1-i): if nums[j] == val: if nums[j] != nums[j+1]: nums[j], nums[j+1] = nums[j+1], nums[j] swapped = True if not swapped: break for v in nums: if v != val: count += 1 return count
我的解法: 利用 QuickSort
q27_QuickSort.pyview rawclass Solution: def removeElement(self, nums: List[int], val: int) -> int: if len(nums) == 0: return 0 else: i = 0 j = len(nums)-1 while i != j: while nums[i] != val and i < j: i += 1 while nums[j] == val and i < j: j -= 1 if i < j: nums[i], nums[j] = nums[j], nums[i] if nums[i] == val: return i else: return i+1
其他解法 1
q27解.pyview rawclass Solution: def removeElement(self, nums: List[int], val: int) -> int: count = 0 for i in range(len(nums)): if nums[i] != val: nums[count] = nums[i] count +=1 return count
其他解法 2
q27解2.pyview rawclass Solution: def removeElement(self, nums: List[int], val: int) -> int: i = 0 n = len(nums) while i < n: if nums[i] == val: nums[i] = nums[n-1] n -= 1 else: i += 1 return n