数组:在内存中开辟了一段连续的地址，每一个地址就直接可以通过内存管理器进行访问，访问某一个元素的时间复杂度为o(1),
Java,C++: int a[100];
Python: list=[]
JavaScript: let x = [1,2,3]
array 时间复杂度
| prepend | O(1) |
|---|---|
| append | O(1) |
| lookup | O(1) |
| insert | O(n) |
| delete | O(n) |
Linked List
class LinkedList{
Node head;
class Node {
int data;
Node next;
Node(int d){data = d;}
}
}
linked list时间复杂度
| prepend | O(1) |
|---|---|
| append | O(1) |
| lookup | O(n) |
| insert | O(1) |
| delete | O(1) |
skip list跳表:只能用于元素有序的情况。跳表对标的是平衡树（AVL Tree）和二分查找，是一种插入/删除/搜索都是Olog(n)的数据结构。1989年出现。它最大的优势是原理简单，容易实现，方便扩展，效率更高。因此在一些热门的项目里用来替代平衡树，如Redis、LevelDB等。
一般加速方式是升维，一维变二维,升维思想+空间换时间。
跳表查询的时间复杂度分析:n/2、n/4、n/8、第k级索引结点的个数就是n/(2…k)，假设索引有h级，最高级的索引有2个结点。n/(2h)=2,从而求得h=log2(n)-1;
在跳表中查询任意数据的时间复杂度就是O(logn),空间复杂度为O(n)
跳表时间复杂度
| prepend | O(log2(n)) |
|---|---|
| append | O(log2(n) |
| lookup | O(log2(n) |
| insert | O(log2(n) |
| delete | O(log2(n) |
LRU缓存机制
为什么redis中使用跳表(skiplist)
练习步骤
题目移动零:https://leetcode-cn.com/problems/move-zeroes/
1.5-10分钟:读题和思考
2.有思路:自己开始做和写代码;不然马上看题解！
3.默写背诵、熟练
4.然后开始自己写(闭卷)
5.五遍，五毒神掌
6.去掉cn来到国际站https://leetcode.com/problems/move-zeroes/
移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/move-zeroes
思路:
1.loop count zeros
2.开心数组 loop
3.index
单次循环
void moveZeroes(int* nums, int numsSize){
int i, k;
int j = 0;
for(i = 0;i< numsSize;i++){
if(nums[i] != 0){
nums[i] = k;
nums[j] = nums[i];
k = nums[j];
j++;
}
}
}
两次循环
public void moveZeroes(int[] nums) {
if (nums == null || nums.length == 0) return;
int insertPos = 0;
for (int num: nums) {
if (num != 0) nums[insertPos++] = num;
}
while (insertPos < nums.length) {
nums[insertPos++] = 0;
}
}
滚雪球
class Solution {
public void moveZeroes(int[] nums) {
int snowBallSize = 0;
for (int i=0;i<nums.length;i++){
if (nums[i]==0){
snowBallSize++;
}
else if (snowBallSize > 0) {
int t = nums[i];
nums[i]=0;
nums[i-snowBallSize]=t;
}
}
}
}
有序数组去重
给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。
答案
数组完成排序后，我们可以放置两个指针 ii 和 jj，其中 ii 是慢指针，而 jj 是快指针。只要 nums[i] = nums[j]nums[i]=nums[j]，我们就增加 jj 以跳过重复项。
当我们遇到 nums[j] \neq nums[i]nums[j]，
=nums[i] 时，跳过重复项的运行已经结束，因此我们必须把它（nums[j]nums[j]）的值复制到 nums[i + 1]nums[i+1]。然后递增 ii，接着我们将再次重复相同的过程，直到 jj 到达数组的末尾为止。
。
int removeDuplicates(int* nums, int numsSize){
int j = 0;
nums[j] = nums[0];
for(int i = 1;i<numsSize;i++){
if(nums[i] != nums[j]){
j++;
nums[j] = nums[i];
}
}
return j+1;
}
盛最多水的容器
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
class Solution {
public int maxArea(int[] height) {
int res = 0;
int i = 0;
int j = height.length-1;
while(i<j){
int area = (j-i)* Math.min(height[i],height[j]);
res = Math.max(area,res);
if(height[i] < height[j]){
i++;
}else{
j--;
}
}
return res;
}
}
空间复杂度
1.数组的长度
2.递归的深度
网友评论