数组基础
数组基础
- 把数据码成一排进行存放
索引可以有语义也可以没有语义
我们先来看一个简单的数组
package arithmetic;
public class main {
public static void main(String[] args) {
int[] arr = new int[10];
for (int i = 0; i < arr.length; i++) {
arr[i] = i;
}
int[] scores = new int[]{100,99,98};
for (int i=0;i<scores.length;i++){
System.out.println(scores[i]);
}
for(int score : scores){
System.out.println(score);
}
}
}
相信大家对上面这段代码在了解不过了。
- 数组最大的优点：快速查询
- 数组最好应用于“索引有语义”的情况
- 但并非所有有语义的所有都适用于数组
比如：身份证号：10101010181829182 - 这里我们主要处理“索引没有语义”的情况数组的使用
制作属于我们自己的数组类
- 索引没有语义，如何表示没有元素？
- 如何添加元素？如何删除元素？
- 。。。。
- 基于java的数组，二次封装属于我们自己的数组类
增 删 改 查
capacity（容量），size（大小）
看下面代码????
package arithmetic;
public class Array {
private int[] data;
private int size;
//构造函数，传入数组的容量capacity构造Array
public Array(int capacity) {
data = new int[capacity];
size = 0;
}
//无参构造函数，默认数组的容量capa=10
public Array() {
this(10);
}
//获取数组中的元素个数
public int geySiaze() {
return size;
}
//获取数组的容量
public int getCapacity() {
return data.length;
}
public boolean isEmpty() {
return size == 0;
}
//获取数组容量
public void addLast(int e) {
// if (size == data.length)
// throw new IllegalArgumentException("AddLast failed.Array is full");
// data[size] = e;
// size++;
//有了add方法就不需要在写上面的代码了
add(size, e);
}
public void addFirst(int e) {
//有了add方法就直接调用就行了
add(0, e);
}
//在第index个位置插入一个新元素e
public void add(int index, int e) {
if (size == data.length)
throw new IllegalArgumentException("Add failed . Array is full");
if (index < 0 || index > size)
throw new IllegalArgumentException("add failed .Require index > 0 and index < size ");
for (int i = size - 1; i >= index; i--)
data[i + 1] = data[i];
data[index] = e;
size++;
}
//获取第index个元素
int get(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("get failed ,index is illegal.");
return data[index];
}
//设置索引为index的元素值为e
void set(int index, int e) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("get failed ,index is illegal.");
data[index] = e;
}
//查找数组中是否有元素e
public boolean contains(int e) {
for (int i = 0; i < size; i++) {
if (data[i] == e) {
return true;
}
}
return false;
}
//查找数组中元素e所在的索引的位置，如果不存在元素e，则返回-1
public int find(int e) {
for (int i = 0; i < size; i++) {
if (data[i] == e) {
return i;
}
}
return -1;
}
//从数组中删除index位置的元素，返回删除的元素
public int remove(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("remove failed ,index is illegal.");
int ret = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
size--;
return ret;
}
//从数组中删除第一个元素，返回删除的元素
public int removeFirst() {
return remove(0);
}
//从数组中删除最后一个元素，返回删除的元素
public int removeLast() {
return remove(size - 1);
}
public void removeElement(int e) {
int index = find(e);
if (index != -1)
remove(index);
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
stringBuilder.append("[");
for (int i = 0; i < size; i++) {
stringBuilder.append(data[i]);
if (i != size - 1)
stringBuilder.append(",");
}
stringBuilder.append(']');
return stringBuilder.toString();
}
}
这段代码相信大家也很容易看懂，看不懂的请认真看注释????,注释写的很明了
使用泛型
- 让我们的数据结构可以防止“任何”数据类型
- 不可以是基本数据类型，只能是类对象
boolean，byte，char，short，int，long，float，double - 每个基本类型都可以有对应的包装类
Boolean，Byte，Char，Short，Integer，Long，Float，Double
下面把上面那段代码改成泛型
package arithmetic;
public class Array<E> {
private E[] data;
private int size;
//构造函数，传入数组的容量capacity构造Array
public Array(int capacity) {
data = (E[]) new Object[capacity];
size = 0;
}
//无参构造函数，默认数组的容量capa=10
public Array() {
this(10);
}
//获取数组中的元素个数
public int geySiaze() {
return size;
}
//获取数组的容量
public int getCapacity() {
return data.length;
}
public boolean isEmpty() {
return size == 0;
}
//获取数组容量
public void addLast(E e) {
// if (size == data.length)
// throw new IllegalArgumentException("AddLast failed.Array is full");
// data[size] = e;
// size++;
//有了add方法就不需要在写上面的代码了
add(size, e);
}
public void addFirst(E e) {
//有了add方法就直接调用就行了
add(0, e);
}
//在第index个位置插入一个新元素e
public void add(int index, E e) {
if (size == data.length)
throw new IllegalArgumentException("Add failed . Array is full");
if (index < 0 || index > size)
throw new IllegalArgumentException("add failed .Require index > 0 and index < size ");
for (int i = size - 1; i >= index; i--)
data[i + 1] = data[i];
data[index] = e;
size++;
}
//获取第index个元素
E get(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("get failed ,index is illegal.");
return data[index];
}
//设置索引为index的元素值为e
void set(int index, E e) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("get failed ,index is illegal.");
data[index] = e;
}
//查找数组中是否有元素e
public boolean contains(E e) {
for (int i = 0; i < size; i++) {
if (data[i] == e) {
return true;
}
}
return false;
}
//查找数组中元素e所在的索引的位置，如果不存在元素e，则返回-1
public int find(E e) {
for (int i = 0; i < size; i++) {
if (data[i] == e) {
return i;
}
}
return -1;
}
//从数组中删除index位置的元素，返回删除的元素
public E remove(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("remove failed ,index is illegal.");
E ret = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
size--;
data[size] = null; //loitering objects != memory leak
return ret;
}
//从数组中删除第一个元素，返回删除的元素
public E removeFirst() {
return remove(0);
}
//从数组中删除最后一个元素，返回删除的元素
public E removeLast() {
return remove(size - 1);
}
public void removeElement(E e) {
int index = find(e);
if (index != -1)
remove(index);
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
stringBuilder.append("[");
for (int i = 0; i < size; i++) {
stringBuilder.append(data[i]);
if (i != size - 1)
stringBuilder.append(",");
}
stringBuilder.append(']');
return stringBuilder.toString();
}
}
改成泛型之后就能支持所有的类型，看下面的例子：
package arithmetic.array;
public class Student {
private String name;
private int score;
public Student(String name, int score) {
this.name = name;
this.score = score;
}
@Override
public String toString() {
return String.format("Student (name : %s,score: %d)" ,name , score);
}
public static void main(String[] args) {
Array<Student> array = new Array<>();
array.addLast(new Student("a",100));
array.addLast(new Student("b",99));
array.addLast(new Student("c",88));
System.out.println(array);
}
}
动态数组
上面的数组已经满了，如果再添加一个元素的话，按照现在的逻辑肯定会抛出异常。
那么我们开辟一个更大的空间，把上面的数组中的元素全部放入新的数组中（这就是扩容）
用代码实现
//在第index个位置插入一个新元素e
public void add(int index, E e) {
if (index < 0 || index > size)
throw new IllegalArgumentException("add failed .Require index > 0 and index < size ");
if (size == data.length)
//throw new IllegalArgumentException("Add failed . Array is full");
resize(2 * data.length);
for (int i = size - 1; i >= index; i--)
data[i + 1] = data[i];
data[index] = e;
size++;
}
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i=0;i<size;i++){
newData[i] = data[i];
}
data = newData;
}
现在又有问题了，如果删除元素，那么空间是会造成浪费的
只需要在remove方法中加入如下代码：
if (size == data.length / 2)
resize(data.length / 2);
简单的时间复杂度分析
- O(1) ,o(n),o(lgn),o(nlogn),o(n^2)
- 大o描述的是算法的运行时间和输入数据之间的关系
- 为什么要用大O，叫做O(n),忽略常数。实际时间T=c1*n+c2
-
- 添加操作
addLast(e) o(1)
addFirst(e) o(n)
add(index,e)
严格计算需要一些概率论知识 - 删除操作
removeLast(e) O(1)
removeFirst(e) o(n)
remove(index,e) o(n/2) = o(n) - 修改操作
set(index,e) o(1) - 查找操作
get(index) o(1)
contains(e) o(1)
find(e) o(n)
动态数组 - 增：o(n) 如果只对最后一个元素操作
- 删：o(n) 依然是o(n)？因为resize？
- 改：已知索引o(1);未知索引o(n)
- 查：已知索引o(1);未知索引o(n)
resize的复杂度分析
resize o(n)
9次addLast操作，触发resize，总共进行了17次基本操作
平均，每次addLAst操作，进行2次基本操作
假设capacity=n,n+1次addLast，触发resize，总共进行2n+1次基本操作
平均，每次addLast操作，进行2次基本操作
这样均摊计算，时间复杂度是0(1)的
在这个例子里，这样均摊就算，比计算最坏情况有意义
addLast的均摊复杂度为O(1)
同理，我们看removeLast操作，均摊复杂度也为o(1)
复杂度震荡
但是，当我们同事看到addLast和removeLast操作：
出现问题的原因：removeLast和resize过于着急（Eager）
解决方案：lazy
当size ==capacoty/4时，才将capacity减半
所以现在只需要把remove的代码稍微该一下
//从数组中删除index位置的元素，返回删除的元素
public E remove(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("remove failed ,index is illegal.");
E ret = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
size--;
data[size] = null; //loitering objects != memory leak
if (size == data.length / 4 && data.length / 2 != 0)
resize(data.length / 2);
return ret;
}//从数组中删除index位置的元素，返回删除的元素
public E remove(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("remove failed ,index is illegal.");
E ret = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
size--;
data[size] = null; //loitering objects != memory leak
if (size == data.length / 4 && data.length / 2 != 0)
resize(data.length / 2);
return ret;
}