Li Kou brush question diary /day6/6.28

Novice Village

Delete duplicate elements in an ordered array , Double finger needling

This method has two requirements , Modify the original array , Do not use other arrays

If the length of the array is 0;

Output directly

If the length of the array is not 0;

Set two pointers ,fast and slow,fast and slow The initial value for the 1, Because to compare fast and fast-1 The elements of

fast Used to traverse all array element subscripts ,slow Used to record the number of unique elements

When fast-1 and fast The elements pointed to are different , take fast The elements represented are given to slow Represents the elements of , And will ++slow,++fast

When fast and fast-1 Point to the same element ,++fast,slow unchanged

Such as below , When the cycle starts for the first time ,fast-=1, Represents the elements of 0, and fast-1 The elements represented are the same , here ,fast Keep going right ,slow unchanged .

 

fast=2 when , At this time, the element pointed to is 1, and fast-1 Pointing elements 0 Different , At this time will be fast Pointing elements 1 Assign to slow Pointing elements ,nums[slow]=nums[fast], And will slow Move to the right ,++slow,fast Keep going right ,++fast

 

 

Keep going ......

until fast=9 when （n=10,fast<n）, take nums[9] The value is assigned to nums[4],++slow=5, At this time will be nums[slow] Output , Is an array that eliminates duplicate elements .

slow Is the length of the new array , It is modified on the basis of the original array .

Example

  Their thinking ： Above

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n == 0) {    // Determine whether the length of the array is 0
            return 0;
        }
        int fast = 1, slow = 1;    // Set two speed pointers 
        while (fast < n) {        // The length of the array is n, Then the position of the element at the end is n-1
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                ++slow;    // Finally, output the length of the non repeating array , So choose ++slow
            }
            ++fast;    // Prevent illegal entry into the cycle 
        }
        return slow;    // Returns the length of a non repeating array 
    }
}

Other ideas ：

foreach Traverse (for every last )

jdk5.0 New characteristics , new for loop

for(type x:type Y)

Traverse Array or collection Y The elements of , Each iteration assigns the element value to x

for example

for(int num:nums)

Is to put nums This array is traversed , How many numbers does it have , Just traverse how many times .

When traversing, one of the values is given to num;

foreach have access to for Statement substitution

for(int i =0;i<nums.length;i++){

    System.out.print(nums[i]+" ");

}

General idea ：

 

class Solution {
    public int removeDuplicates(int[] nums) {   
        return process(nums, 1);
    }
    int process(int[] nums, int k) {
        int idx = 0; 
        for (int x : nums) {
            if (idx < k || nums[idx - k] != x) nums[idx++] = x;
        }
        return idx;
    }
}

The last two ideas quote leetcode Content of shanggongshui Sanye blogger , If there is any infringement , Contact deletion