上海本地新闻,湛江seo排名,wordpress无法加载预览图片,帮企业建设网站和推广网站1.. 数组基础数组就是把数据码成一排进行存放。Java中#xff0c;数组的每个元素类型必须相同#xff0c;可以都为int类型#xff0c;string类型#xff0c;甚至是自定义类型。数组的命名要语义化#xff0c;例如#xff0c;如果数组用来存放学生的成绩#xff0c;那么命… 1.. 数组基础 数组就是把数据码成一排进行存放。 Java中数组的每个元素类型必须相同可以都为int类型string类型甚至是自定义类型。 数组的命名要语义化例如如果数组用来存放学生的成绩那么命名为scores就比较合适。 索引index是数组中的一个重要概念它是我们给数组中的每个元素分配的编号从0开始依次递增。如果数组中存放了n个元素第一个元素的索引是0最后一个元素的索引是n-1。 通过索引我们可以对数组中的元素进行快速访问例如我们访问索引为2的元素也就是数组中的第3个元素就可以通过scores[2]这种形式。 在Java中声明一个简单的数组 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;}
} 声明一个有初始值的数组 public class Main {public static void main(String[] args) {int[] scores new int[]{100, 99, 86};for (int i 0; i scores.length; i)System.out.println(scores[i]);}
} for循环的另一种使用形式 public class Main {public static void main(String[] args) {int[] scores new int[]{100, 99, 86};for (int score : scores)System.out.println(score);}
} 修改数组中的元素 socres[1] 98; 数组的索引可以是语义化的也可以是非语义化的。 数组的最大优点就是可以通过索引对数据进行快速查询因此我们倾向于使用语义化的索引这样我们就很清楚自己在查什么。 如果我们的应用场景中索引没有语义那么使用其它数据结构可能是更好的选择。 对于一些特殊应用场景虽然使用了语义化索引但依然不适合使用数组例如身份证号我们不能使用身份证号来作为数组的索引因为这个数字太大了会导致巨大的空间浪费。 如果数组的索引是非语义化的我们就需要考虑很多问题例如当数组的空间未被填满时如何表示空位处的元素如何向数组中添加新的元素如何删除掉数组中原有的元素等等。Java所提供的原生数组是无法解决这些问题的我们需要定制属于自己的数组类Array即基于Java的原生数组二次封装属于我们自己的数组类。 2.. 实现自定义数组类Array所包含的基本方法 public class Array {private int[] data; //设置为private不希望用户从外部直接获取这些信息防止用户篡改数据private int size;//构造函数传入数组的容量capacity构造Arraypublic Array(int capacity) {data new int[capacity];size 0;}//无参数构造函数默认数组容量capacity10public Array() {this(10); //这里的capacity是IDE自动添加的提示信息实际不存在}//获取数组中的元素个数public int getSize() {return size;}//获取数组的容量public int getCapacity() {return data.length;}//判断数组是否为空public boolean isEmpty() {return size 0;}
} 3.. 实现向自定义数组中添加元素的方法 向数组中添加元素的最简单的方法就是向数组的末尾添加元素 //向数组末尾添加一个新元素
public void addLast(int e) {if (size data.length) {throw new IllegalArgumentException(AddLast failed. Array is full.);}data[size] e;size;
} 向数组中指定索引位置插入一个元素 //在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;
} 定义完向数组中指定索引位置插入一个元素的方法add之后我们之前定义的向数组末尾插入元素的方法addLast其实可以调用add方法来实现我们调整addLast方法如下 //向数组末尾添加一个新元素
public void addLast(int e) {add(size, e);
} 我们还可以调用add方法实现一个向数组开头添加一个新元素的方法 //向数组开头添加一个新元素
public void addFirst(int e) {add(0, e);
} 4.. 实现在数组中查询元素和修改元素的方法 实现自定义打印数组格式 Override
public String toString() { //覆盖父类的toString方法
StringBuilder res new StringBuilder();res.append(String.format(Array: size%d, capacity%d\n, size, data.length));res.append([);for (int i 0; i size; i) {res.append(data[i]);if (i ! size - 1) {res.append(, );}}res.append(]);return res.toString();
} 在main函数中进行测试 public class Main {public static void main(String[] args) {Array arr new Array(20);for (int i 0; i 10; i) {arr.addLast(i); //测试addLast方法}System.out.println(arr);arr.add(1, 100); //测试add方法System.out.println(arr);arr.addFirst(-1); //测试addFirst方法System.out.println(arr);}} 打印效果如下 Array: size10, capacity20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size11, capacity20
[0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size12, capacity20
[-1, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9] 实现获取指定索引元素的方法 //获取index位置的元素
public int get(int index) {if (index 0 || index size) {throw new IllegalArgumentException(Get failed. Index is illegal.);}return data[index];
} 实现修改指定索引元素的方法 //修改index位置的元素为e
public void set(int index, int e) {if (index 0 || index size) {throw new IllegalArgumentException(Set failed. Index is illegal.);}data[index] e;
} 实现查看数组中是否包含元素e的方法 //查找数组中是否存在元素e
public boolean contains(int e) {for (int i 0; i size; i) {if (data[i] e) {return true;}}return false;
} 实现查看数组中指定元素的索引的方法若找不到返回-1 //查看数组中元素e的索引若找不到元素e返回-1
public int find(int e){for(int i0;isize;i){if(data[i] e){return i;}}return -1;
} 实现删除数组中指定索引的元素的方法 //删除掉index位置的元素并且返回所删除的元素
public int remove(int index) {if (index 0 || index size) {throw new IllegalArgumentException(Add failed. Require index 0 and index size);}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);
}//如果数组中有元素e那么将其删除否则什么也不做
public void removeElement(int e) {int index find(e);if (index ! -1) {remove(index);}
} 5.. 整理我们目前实现的业务逻辑 public class Array {private int[] data; //设置为private不希望用户从外部直接获取这些信息防止用户篡改数据private int size;//构造函数传入数组的容量capacity构造Arraypublic Array(int capacity) {data new int[capacity];size 0;}//无参数构造函数默认数组容量capacity10public Array() {this(10); //这里的capacity是IDE自动添加的提示信息实际不存在}//获取数组中的元素个数public int getSize() {return size;}//获取数组的容量public int getCapacity() {return data.length;}//判断数组是否为空public boolean isEmpty() {return size 0;}//向数组末尾添加一个新元素epublic void addLast(int e) {add(size, e);}//向数组开头添加一个新元素epublic void addFirst(int e) {add(0, e);}//在index位置插入一个新元素epublic 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位置的元素public int get(int index) {if (index 0 || index size) {throw new IllegalArgumentException(Get failed. Index is illegal.);}return data[index];}//修改index位置的元素为epublic void set(int index, int e) {if (index 0 || index size) {throw new IllegalArgumentException(Set failed. Index is illegal.);}data[index] e;}//查找数组中是否存在元素epublic boolean contains(int e) {for (int i 0; i size; i) {if (data[i] e) {return true;}}return false;}//查看数组中元素e的索引若找不到元素e返回-1public 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);}//如果数组中有元素e那么将其删除否则什么也不做public void removeElement(int e) {int index find(e);if (index ! -1) {remove(index);}}Overridepublic String toString() { //覆盖父类的toString方法
StringBuilder res new StringBuilder();res.append(String.format(Array: size%d, capacity%d\n, size, data.length));res.append([);for (int i 0; i size; i) {res.append(data[i]);if (i ! size - 1) {res.append(, );}}res.append(]);return res.toString();}
} 6.. 现在我们的自定义数组的元素只允许为int类型我们需要进行优化让数组可以放置任意类型的元素解决这个问题的技术称之为泛型。这里的任意加了引号这是因为在Java中一个泛型类并不能放置任意数据类型的元素泛型不能放置基本数据类型只能放置类对象。在Java中共有8中基本数据类型int、short、long、boolean、byte、char、float、double。如果将数组设置成泛型数组那么就无法放置这些基本数据类型了。为了解决这个问题Java语言为每个基本数据类型都设计了一个包装类把本来不是类对象的数据包装成了类对象。这8中基本数据类型所对应的包装类分别为Int、Short、Long、Boolean、Byte、Char、Float、Double在需要的情况下包装类与其对应的基本数据类型可以自动进行转换。 7.. 优化后Array类的业务逻辑如下 public class ArrayE {private E[] data; //设置为private不希望用户从外部直接获取这些信息防止用户篡改数据private int size;//构造函数传入数组的容量capacity构造Arraypublic Array(int capacity) {data (E[]) new Object[capacity];size 0;}//无参数构造函数默认数组容量capacity10public Array() {this(10); //这里的capacity是IDE自动添加的提示信息实际不存在}//获取数组中的元素个数public int getSize() {return size;}//获取数组的容量public int getCapacity() {return data.length;}//判断数组是否为空public boolean isEmpty() {return size 0;}//向数组末尾添加一个新元素epublic void addLast(E e) {add(size, e);}//向数组开头添加一个新元素epublic void addFirst(E e) {add(0, e);}//在index位置插入一个新元素epublic 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位置的元素public E get(int index) {if (index 0 || index size) {throw new IllegalArgumentException(Get failed. Index is illegal.);}return data[index];}//修改index位置的元素为epublic void set(int index, E e) {if (index 0 || index size) {throw new IllegalArgumentException(Set failed. Index is illegal.);}data[index] e;}//查找数组中是否存在元素epublic boolean contains(E e) {for (int i 0; i size; i) {if (data[i].equals(e)) {return true;}}return false;}//查看数组中元素e的索引若找不到元素e返回-1public int find(E e) {for (int i 0; i size; i) {if (data[i].equals(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]会指向一个类对象这部分空间不会被释放loitering objectsdata[size] null;return ret;}//删除掉数组开头的元素并返回删除的元素public E removeFirst() {return remove(0);}//删除掉数组末尾的元素并返回删除的元素public E removeLast() {return remove(size - 1);}//如果数组中有元素e那么将其删除否则什么也不做public void removeElement(E e) {int index find(e);if (index ! -1) {remove(index);}}Overridepublic String toString() { //覆盖父类的toString方法
StringBuilder res new StringBuilder();res.append(String.format(Array: size%d, capacity%d\n, size, data.length));res.append([);for (int i 0; i size; i) {res.append(data[i]);if (i ! size - 1) {res.append(, );}}res.append(]);return res.toString();}
} 8.. 再次在main方法中实例化我们的自定义数组进行测试 public class Main {public static void main(String[] args) {ArrayInteger arr new Array(20);for (int i 0; i 10; i) {arr.addLast(i);}System.out.println(arr);arr.add(1, 100);System.out.println(arr);arr.addFirst(-1);System.out.println(arr);arr.remove(2);System.out.println(arr);arr.removeElement(4);System.out.println(arr);arr.removeFirst();System.out.println(arr);arr.removeLast();System.out.println(arr);}
} 输出结果如下 Array: size10, capacity20
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size11, capacity20
[0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size12, capacity20
[-1, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size11, capacity20
[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size10, capacity20
[-1, 0, 1, 2, 3, 5, 6, 7, 8, 9]
Array: size9, capacity20
[0, 1, 2, 3, 5, 6, 7, 8, 9]
Array: size8, capacity20
[0, 1, 2, 3, 5, 6, 7, 8] 9.. 测试让自定义数组去承载对象 public class Student {private String name;private int score;public Student(String studetName, int studentScore) {name studetName;score studentScore;}Overridepublic String toString() {return String.format(Student(name: %s, score: %d), name, score);}public static void main(String[] args) {ArrayStudent arr new Array();arr.addLast(new Student(XueZou, 98));arr.addLast(new Student(Guiche, 100));arr.addLast(new Student(QUiShui, 99));System.out.println(arr);}
} 输出结果如下 Array: size3, capacity10
[Student(name: XueZou, score: 98), Student(name: Guiche, score: 100), Student(name: QUiShui, score: 99)] 10.. 动态数组即数组的容量可伸缩 修改add方法的业务逻辑使自定义数组支持扩容 //在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) {resize(2 * size); //扩大为原容量的2倍}for (int i size - 1; i index; i--) {data[i 1] data[i];}data[index] e;size;
} 我们需要实现resize方法业务逻辑如下 private void resize(int newCapacity) {E[] newData (E[]) new Object[newCapacity];for (int i 0; i size; i) {newData[i] data[i];}data newData;
} 实现扩容后进行测试 public static void main(String[] args) {ArrayInteger arr new Array();for (int i 0; i 10; i) {arr.addLast(i);}System.out.println(arr);arr.add(1, 100);System.out.println(arr);arr.addFirst(-1);System.out.println(arr);
} 输出效果如下 Array: size10, capacity10
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size11, capacity20
[0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size12, capacity20
[-1, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9] 修改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]会指向一个类对象这部分空间不会被释放loitering objectsdata[size] null;if (size data.length / 2) {resize(data.length / 2); //被利用的空间等于总空间的一半时将数组容量减少一半}return ret;
} 实现自动降低容量后进行测试 public static void main(String[] args) {ArrayInteger arr new Array();for (int i 0; i 10; i) {arr.addLast(i);}System.out.println(arr);arr.add(1, 100);System.out.println(arr);arr.addFirst(-1);System.out.println(arr);arr.remove(2);System.out.println(arr);arr.removeElement(4);System.out.println(arr);arr.removeFirst();System.out.println(arr);
} 输出效果如下 Array: size10, capacity10
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size11, capacity20
[0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size12, capacity20
[-1, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size11, capacity20
[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array: size10, capacity10
[-1, 0, 1, 2, 3, 5, 6, 7, 8, 9]
Array: size9, capacity10
[0, 1, 2, 3, 5, 6, 7, 8, 9] 11.. 简单的时间复杂度分析 O(1), O(n), O(lgn), O(nlgn), O(n^2) 大O描述的是算法的运行时间和输入数据之间的关系 通常我们会说下面的这段代码的算法是O(n)的n在这里简单理解为nums中的元素个数O(n)是说下面这段代码的运行效率与nums中的元素个数n是呈线性关系的线性关系体现在n是一次方。 public static int sum(int[] nums) {int sum 0;for (int num: nums) {sum num;return sum;} 按照这个思路我们对上面所实现的方法挨个分析一下它们的算法的时间复杂度添加操作中addLast(e)方法的时间复杂度是O(1)这表示我们的算法所消耗的时间与我们数据的规模没有关系这里所指的数据规模是我们数组中的元素个数addFirst(e)方法的时间复杂度是O(n)因为每个元素都需要向后移动一位add(index, e)方法的时间复杂度与index的具体取值相关它的时间复杂度也是O(n)综合来看添加操作是一个O(n)级别的算法。 删除操作中removeLast(e)方法的时间复杂度是O(1)removeFirst(e)的时间复杂度是O(n)remove(index, e)的时间复杂度也是O(n)综合来看删除操作的时间复杂度也是O(n)。 修改操作set(index, e)的时间复杂度是O(1)这是数组的最大优势专业术语称为支持随机访问。 查询操作中get(index)方法的时间复杂度是O(1)find(e)方法和contains(e)方法的时间复杂度都是O(n)。 12.. 总的来看对于动态数组来说增删改查四种操作 增时间复杂度O(n); 删时间复杂度O(n); 改已知索引O(1)未知索引O(n); 查已知索引O(1)未知索引O(n); 因此索引具有语义时选择数组是非常好的我们可以通过索引轻松检索数据中的内容。 13.. resize的时间复杂度分析 对于添加操作如果我们只使用addLast方法那么它的时间复杂度本来应该是O(1)但是由于存在resize方法而resize方法的时间复杂度是O(n)所以addLast方法的时间复杂度就不是O(1)了但是它的均摊复杂度是O(1); 类似的对于删除操作如果只使用removeLast方法那么它的均摊复杂度也是O(1); 14.. 复杂度震荡 复杂度震荡是指我们在数组容量的临界位置交替进行添加和删除操作这会导致数组不断执行扩容和缩容操作而扩容和缩容的时间复杂度都是O(n)出现这种问题的原因在于我们执行removeLast方法后resize得有点着急(Eager)解决方案是使用更加懒惰的策略(Lazy)简单理解就是当数组占用量刚好减到1/2时不着急缩容等减到1/4时再触发缩容只缩1/2。 我们需要稍微改动一下remove方法如下所示 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]会指向一个类对象这部分空间不会被释放loitering objectsdata[size] null;if (size data.length / 4 data.length / 2 ! 0) { //改动在这里resize(data.length / 2); //被利用的空间等于总空间的一半时将数组容量减少一半}return ret;
} 转载于:https://www.cnblogs.com/xuezou/p/9276945.html
