An array is a data structure composed of a collection of elements of the same type, and a contiguous memory is allocated for storage. The index of the element can be used to calculate the storage address corresponding to the element. (Wikipedia)
1. Storage structure
Array is a linear table data structure. When the array is defined, the system will allocate A contiguous memory space to store a group of the same type of data, such as int num[n];
2. Multidimensional array
Array is defined as one-dimensional array, two-dimensional array, three-dimensional array…n-dimensional Array, its format can be written as int num[n][m];
3. Time complexity of finding, inserting, and deleting
3.1 When you need to find the Kth number of an array, the array will be accessed according to the subscript. The time complexity of the search is O(1)
3.2 Need to insert a number Y into the Kth number of the array. In the case of an ordered array, the time complexity of insertion is O(n)
void ArrayAdd(int* pNum, int nCount, int nAddIndex, int nAddNum) {
int nEnd = nAddIndex-1;
for(int nIndex=nCount-1; nIndex>=nEnd; nIndex—) {
pNum[nIndex+1] = pNum[nIndex];
}
pNum[nEnd] = nAddNum;
}
3.3 Need to delete the Kth number of the array, the time complexity is O(n)
void ArrayDelete(int* pNum, int nCount, int nDeleteIndex) {
int nStart = nDeleteIndex-1;
int nEnd = nCount-1;
for(int nIndex=nStart; nIndex) { = pNum[nIndex+1];
pNum[nIndex]
}
}
4. Array out of bounds
If the array definition is int num[n], you can operate on data from 0 to (n-1), but If the data after n is operated, the array will be out of bounds, and the operation is not the data of num but other data.
Yes Follow the official account to learn more interview techniques
void ArrayAdd(int* pNum, int nCount, int nAddIndex, int nAddNum) {
int nEnd = nAddIndex-1;
for(int nIndex=nCount-1; nIndex>=nEnd; nIndex—) {
pNum[nIndex+1] = pNum[nIndex];
}
pNum[nEnd] = nAddNum;
}
void ArrayDelete(int* pNum, int nCount, int nDeleteIndex) {
int nStart = nDeleteIndex-1;
int nEnd = nCount-1;
for(int nIndex=nStart; nIndex) {
pNum[nIndex] = pNum[nIndex+1];
}
}