This is the fourth day of my participation in the November Gwen Challenge. See details: The last Gwen Challenge 2021.

Give permutations to build arrays

1. Title Description

Give you a permutation nums starting at 0 (subscripts also starting at 0). Construct ans of the same length, where ans[I] = nums[nums[I]] for each I (0 <= I < nums.length). Returns the constructed array ANS.

The permutation nums from 0 is an array of different integers from 0 to nums. length-1 (0 and nums. length-1 are included).

Example 1:

Input: nums = [0,2,1,5,3,4] ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]] = [nums[0], nums[2], Nums nums [1], [5], nums [3], nums =,1,2,4,5,3 [0] [4]] example 2:

Input: nums = [5,0,1,2,3,4] ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]] = [nums[5], nums[0], Nums nums [1], [2], nums [3], nums =,5,0,1,2,3 [4] [4]]

Second, the topic analysis

This kind of question, don’t want to say a word

Three, code,

1. java

class Solution {
    public int[] buildArray(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        for (int i=0; i<n; i++){ ans[i] = nums[nums[i]]; }returnans; }}Copy the code

2. python

class Solution:
    def buildArray(self, nums: List[int]) - >List[int] :
        n = len(nums)
        ans = [0]*n
        for i in range(n):
            ans[i] = nums[nums[i]]
        return ans
Copy the code

Removes duplicates from an ordered array

1. Topic description

Give you an ordered array nums, ask you to delete the repeated elements in place, so that each element appears only once, return the deleted array after the new length.

Instead of using extra array space, you must modify the input array in place and do so with O(1) extra space.

Description:

Why is the return value an integer, but the output answer is an array?

Note that the input array is passed “by reference,” which means that modifying the input array in a function is visible to the caller.

You can imagine the internal operation as follows:

// Nums is passed by reference. That is, do not make any copies of the arguments
int len = removeDuplicates(nums);

// Modifying the input array in a function is visible to the caller.
// Depending on the length returned by your function, it prints out all elements in the array within that length.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
Copy the code

Example 1:

Input: nums = [1,1,2] Output: 2, nums = [1,2] Explanation: The function should return a new length of 2, and the first two elements of the original array nums are changed to 1,2. You don’t need to worry about the element after the new length in the array. Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4] Output: 5, nums = [0,1,2, 2,3,4] Explanation: The function should return a new length of 5, and the first five elements of the original array NUMs are modified to 0,1,2,3,4. You don’t need to worry about the element after the new length in the array.

Tip:

0 <= nums.length <= 3 * 104-104 <= nums[I] <= 104 NUMs are sorted in ascending order

Source: LeetCode link: leetcode-cn.com/problems/re… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

2

We can’t create an array, we can’t create an array

You just modify the array in place, and the array is sorted

I have no choice but to use the double-pointer method

Double pointer:

  • Create a value that records the length of the new array, starting at 1

  • A pointer moves with the array subscript

  • Another pointer records the number of non-repeating elements

  • Through the array

  • Creates a statement that determines whether the current subscript element and the next subscript element want to wait

  • If not, assign the next index element to m and set m+1

  • Return the value of m when the operation is complete

3. Code

1. python

class Solution:
    def removeDuplicates(self, nums: List[int]) - >int:
        m = 1
        for i in range(len(nums)-1) :ifnums[i] ! = nums[i+1]:
                nums[m] = nums[i+1]
                m += 1
        return m
Copy the code

2. java

class Solution {
    public int removeDuplicates(int[] nums) {
        int m = 1;
        int n = (nums.length)-1;
        for (int i=0; i<n; i++){if(nums[i] ! = nums[i+1]){
                nums[m] = nums[i+1]; m++; }}returnm; }}Copy the code