Array of leetcode brushing titles (constant space for numbers, maximum dictionary order, delete targets, delete duplicates)

Off-topic topic: The year of the heptagon in 2020 was a bad start, with all parts of the world being harmed by nature.This winter holiday epidemic in Wuhan is painful, and Kobe has also suffered misfortunes.In any case, I hope we can get through this difficult time. In the spring blossom season, I wish you and I have a good time and hope that human beings can cherish life and protect nature.

--------------------------------------------------------

1. Title 1 Description:
Gives an array of unordered integers and finds the smallest positive integer not in the given array.
You need to give an algorithm with time complexity in O(n) and constant spatial complexity
Title One Analysis:
Drawing on the ideas of the Great God, the array is first placed in its corresponding position, then the array is traversed. The subscript number of the corresponding position, +1, is the smallest positive integer that does not exist in the array. If all exist, the subscript number of the array, +1.
The code is as follows:

public class Solution {
    public int firstMissingPositive(int[] A) {
        int n = A.length;
        //Traversing through an array places the corresponding number in its place
        for(int i=0;i<n;i++ ){
            while(A[i]>0 && A[i]<=n && A[i]!=A[A[i]-1]){
                int tmp = A[A[i]-1];
                A[A[i]-1]=A[i];
                A[i] = tmp;
            }
        }
        //Find the first element whose location does not match
        for(int i=0;i<n;i++){
            if(A[i]!=i+1)return i+1;
        }
        return n+1;
    }
}

2. Title 2 Description:
Implement the next permutation function: rearrange the numbers in the permutation to the next larger permutation in the dictionary order.Rearrange the numbers in the permutation to the next larger permutation in the dictionary order.
If such an arrangement does not exist, then it is ranked as the lowest in dictionary order (ascending)
Local algorithm is needed to solve this problem, no additional memory space can be requested
Topic 2 Analysis:
The God thought: first find the array from the back to the front, if it has been increasing, then invert the array, otherwise find the position I of the first element that does not satisfy the condition of increasing, continue to traverse backwards and forwards, find the first element that is greater than the position before i-1, and exchange the two numbers. Inverse the elements after I is required.
The code is as follows:

public class Solution {
    public void nextPermutation(int[] num) {
         int len = num.length;
	        int i = len-1;
		//Find non-incremental position i from back to front
	        for(;i > 0;i--) {
	        	if(num[i] > num[i-1])	break;
	        }
	        if(i==0) {//Reverse Array if All Reverse Increment Order
	        	orderArray(0,len-1,num);
	        }else {//Find the first element greater than i-1 from the back to the front, swap it with it, and reverse the position after i to output
	        	for(int j=len-1;j>=i;j--) {
		        	if(num[i-1]<num[j]) {
		        		swap(i-1,j,num);
		        		orderArray(i,len-1,num);
		        		break;
		        	}
		        }
	        }
    }
    //Reverse elements at corresponding positions in the array
     public  void orderArray(int left,int right,int[] num) {
     	for(;left < right;left++,right--) {
     		swap(left,right,num);
     	}
	 }
	 //Swap the number in the i position of the array with the number in the j position
	 public  void swap(int i,int j,int[] num) {
		 int tmp = num[i];
		 num[i] = num[j];
		 num[j] = tmp;
	 }
}

3. Title 3 Description:
Given an array and a value, use the in-place algorithm to delete all elements in the array that equal this value and return the length of the new array.
Topic Three Analysis:
Place all elements equal to elem at the end of the array, using two pointers, one from the front to the back, one from the back to the front and one from the back to the front to compress the array, and the one from the front to the back to find elements equal to the elem, placing them at the right pointer of the array.
The code is as follows:

public class Solution {
    public int removeElement(int[] A, int elem) {
        if(A.length==0) return A.length;
        int left = 0;//Array start position
	     int right = A.length-1;//Array end position
	     if(left==right && A[left]==elem) return 0;
	     while(left < right) {
	         //If the right position is always equal, the right pointer moves to the left, reducing the length of the array
	    	 while(left<right && A[right] == elem) {
	    		 if(right==0) return 0;
	    		 right--;
	    	 }
	    	 //If the left pointer is equal to the elem, swap its elements with the right and move the right pointer to the left to move the compressed array
	    	 if(left<right &&A[left] == elem) {
	    		 swap(left,right,A);
	    		 right--;
	    	 }
	    	 if(left < right) left++;
	     }
	     //If the element pointed to by the current left pointer is equal to elem, then the array length is the value of left, otherwise the array length is the value of left+1
		 return  A[left]==elem?left:left+1;
    }
    //Exchange elements in the i position of the array with elements in the j position
     public  void swap(int i,int j,int[] num) {
		 int tmp = num[i];
		 num[i] = num[j];
		 num[j] = tmp;
	 }
}

4. Title 4 Description:
Given a sorted array, use an in-place algorithm to remove duplicate numbers so that each element in the array appears only once, returning the length of the new array.
You cannot allocate extra space to an array, you must use an in-place algorithm with familiar spatial complexity.
Title 4 Analysis:
With two pointers, the first is used to record the position of the last element of the new array that is currently assembled, the second is used to traverse redundant elements, the second is used to place the element that the second pointer points to at the next position of the first element when it encounters an element that is not equal to the first pointer, the first is always the new array that is assembled, and the second isAt the end of each pointer, the first pointer + 1 is returned, which is the length of the new array.
The code is as follows:

public class Solution {
    public int removeDuplicates(int[] A) {
    	//There are no elements or only one element in the array has no duplicate elements
         if(A.length==0||A.length==1)return A.length;
	     int oneindex = 0;
	     int twoindex = 0;
	     //Select only one element from the array at a time to put it first
	     for(;twoindex < A.length;) {
	    	 if(A[oneindex] == A[twoindex])twoindex++;
	    	 else {
	    		 swap(oneindex+1,twoindex,A);
	    		 oneindex++;
	    		 twoindex++;
	    		 }
	     }
		 return oneindex+1;
    }
    //Swap elements in the i position of the array with elements in the j position
    public  void swap(int i,int j,int[] num) {
		 int tmp = num[i];
		 num[i] = num[j];
		 num[j] = tmp;
	 }
}
39 original articles published, 3 praised, 395 visits
Private letter follow

Tags: Spring

Posted on Thu, 06 Feb 2020 19:09:53 -0800 by Zepo.