O(1) read and write any element in time, with high time efficiency
Implement a simple hash table with an array
Set the index of the array as the key of the hash table
Set no array in the array as the Value of the hash table
In this way, the numbers corresponding to the following table in each table and array form a key value pair, which can be searched in O(1) time
In C + +, when an array is passed as a parameter of a function, the array will automatically degenerate into a pointer of the same type
Title stem:
All numbers in an array of length n are in the range of 0~n-1. Some numbers in the array are repeated, but I don't know how many numbers are repeated, or how many times each number is repeated. Please find the duplicate number in the array
First sort the input array and find out the duplicate numbers from the sorted array, O(nlogn)
public class arrayRepeatNumber { public static void main(String[] args){ int[] num={2,3,1,0,2,5,3}; // int[] num={1,1,2,2,2,2,3,3,4}; quickSort(num,0, num.length-1); locate(num); } public static void quickSort(int[] num,int left,int right){ if(left<right){ int i=left,j=right,x=num[left]; while(i<j){ while(i<j&&num[j]>=x){ j--; } if(i<j){ num[i++]=num[j]; } while(i<j&&num[i]<x){ i++; } if(i<j){ num[j--]=num[i]; } } num[i]=x; quickSort(num,left,i-1); quickSort(num,i+1,right); } } public static void locate(int[] num){ int len= num.length; int point=0; int mark=1; while(point<len-1){ if(num[point]==num[point+mark]){ mark++; } else{ point=point+mark; mark=1; } if(mark==2){ System.out.println(num[point]); } } } }
Scan each number of the array in sequence from beginning to end. When a number is not scanned, you can use the time of O(1) to judge whether the number has been included in hashibati. If there is no such number in the hash table, add it to the hash table. If the number already exists in the hash table, a duplicate number is found. The time complexity of the algorithm is O(n), but at the cost of an O(n) hash table
public static void findRepeatNumber(int[] num) { //Define a collection hashset Set<Integer> set = new HashSet<Integer>(); //Define duplicate Tags int repeat = -1; //Traverse the array for (int i=0;i<num.length;i++) { repeat=-1; //If the addition fails( set Cannot add duplicate elements), indicating that there are duplicate elements if (!set.add(num[i])) { //Repeat mark=Current number repeat = num[i]; } if(repeat!=-1){ System.out.println(repeat); } } }
Space complexity O(1)
If you only need to find one of the duplicate numbers, you can use the subscript method
//Array subscript method public static int subscript(int[] num){ for(int i=0;i< num.length;i++){ while(num[i]!=i){ if(num[i]==num[num[i]]){ return num[i]; } int tmp=num[num[i]]; num[num[i]]=num[i]; num[i]=tmp; } } return -1; }
Stem: in a two-dimensional array, each row is arranged in ascending order from left to right, and each column is arranged in ascending order from top to bottom. Please complete a function, input such a two-dimensional array and an integer, and judge whether the array contains the integer
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
Methods: find the law, observe the matrix, and the numbers are increasing to the right and down. You can start from the top right or bottom left.
① If you start from the upper right element, if the target number is greater than the current element, the row coordinates move to the left. If the target number is less than the current element, the column coordinates move down.
② If you start from the lower left element, if the target number is greater than the current element, the column coordinates move to the right. If the target number is less than the current element, the row coordinates move up.
This code selects the first method
public class matrixSearch { public static boolean matrixSearch(int[][] matrix ,int rows, int columns,int number){ boolean found=false; if(matrix!=null&&matrix.length>=0&&rows>0&&columns>0){ int row=0; int column=columns-1; while(row<rows&&column>=0){ if(matrix[row][column]==number){ found=true; break; } else if(matrix[row][column]>number){//If the current element is larger than the target column--;//Move left to find } else{//If the current element is smaller than the target row++;//Move down to find } } } return found; } public static void main(String[] args){ int[][] num={{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}}; System.out.println(matrixSearch(num,4,4,7)); } }