# Data structure - array

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

Interview question 3 Duplicate number in array

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

Method 1: sorting

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]);
}
}
}
}```

Method 2: hash table

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
//Repeat mark=Current number
repeat = num[i];
}
if(repeat!=-1){
System.out.println(repeat);
}
}
}```

Method 3: subscript mapping

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;
}```

Interview question 4 Find in 2D array

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));
}
}```

Posted by andrewb on Sun, 17 Apr 2022 20:07:03 +0930