Leetcode: array

Day2

The first question is ：27 Remove elements

  Ideas ：

• To know that the elements of an array are contiguous in memory address , You cannot delete an element in an array alone , Can only cover .

solution ：

Solution 1 ： Violence solution （ Two layers of for loop ）

One for Loop through array elements , the second for Loop update array

//  Time complexity ：O(n^2)
//  Spatial complexity ：O(1)
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        for (int i = 0; i < size; i++) {
            if (nums[i] == val) { //  Find the elements that need to be removed , Just move the array forward one bit 
                for (int j = i + 1; j < size; j++) {
                    nums[j - 1] = nums[j];
                }
                i--; //  Because the subscript i All the later values are moved forward by one bit , therefore i Also move forward one bit 
                size--; //  The size of the array -1
            }
        }
        return size;

    }
};

Solution 2 ： Double pointer （ Through a fast pointer and a slow pointer in a for Loop through two for Cycle work ）

Quick pointer ： Find the elements of the new array

Slow pointer ： Subscript to update the new array

//  Time complexity ：O(n)
//  Spatial complexity ：O(1)
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow = 0;
        for (int fast = 0; fast < nums.size(); fast++) {
            if (val != nums[fast]) {
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }
};

The second question is ：977 The square of an ordered array

  Ideas ：

• Violence solution ： First square , Sort according to the obtained data
• Double pointer ：i Point to the starting position ,j Point to the end position ; Put the large values in the new array in reverse order

solution ： Double pointer

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int k = A.size() - 1;
        vector<int> result(A.size(), 0);
        for (int i = 0, j = A.size() - 1; i <= j;) { //  Pay attention here i <= j, Because there are two elements to deal with in the end 
            if (A[i] * A[i] < A[j] * A[j])  {
                result[k--] = A[j] * A[j];
                j--;
            }
            else {
                result[k--] = A[i] * A[i];
                i++;
            }
        }
        return result;
    }
};

summary ：

1、 Double pointer array and linked list operations are very common , A lot of research 、 Linked list 、 Interview questions for string and other operations , They all use double finger acupuncture

2、 Double finger needling can greatly reduce the time complexity , Improve the efficiency of the program