Leetcode learning records (starting from the novice village, you can't kill out of the novice Village) ---1

Array overview

aggregate ： Simply speaking , It can be said to be a whole composed of one or more elements . The types of elements that make up the set can be different , At the same time, these elements are also disordered .

list : It's a linear table . It consists of elements arranged together in a certain order , Is ordered . The common forms of lists are ： Array 、 Linked list 、 Pile up 、 Stack .

Array ： Array introduces the concept of index , You can find the position of the corresponding element by subscript . meanwhile , Due to the subscript , Prove that the data stored in the array is continuous . Unlike arrays , Linked lists are not continuous .

Array reading ： According to the array subscript, you can find the corresponding element , Operate on only one data , So the time complexity is zero O（1）.

Array search ： Consider the worst case , If the data to be searched is at the end , Then you need to start from the 0 The position index goes all the way to the last index of the array . So the time complexity is O（N）.

Array insertion ： If you want to insert this element at the end of the array , Just one step . That is, the computer calculates the memory address of the element to be inserted through the length and position of the array , Then insert the element into the specified position . However , If you want to insert the element elsewhere in the array , There will be a difference , At this time, we first need to make room for the position where the element is to be inserted , Then insert it .

Array deletion ： Deleting an element is similar to inserting an element , When we delete an element in the array , The array will leave vacancy The location of , The elements in the array are continuous in memory , This makes the following elements need to fill the position .

Example 1： Power button https://leetcode-cn.com/problems/find-the-middle-index-in-array/

Just started, I can only traverse （ I feel like I can't get out of the novice village ）