html网站建设购物案例,网站建设中网站需求分析的理解,拘束 wordpress,无锡百度竞价公司一 面试经典#xff1a; 给你一个文件里面包含全国人民#xff08;14亿#xff09;的年龄数据#xff08;0~180#xff09;#xff0c;现在要你统计每一个年龄 有多少人#xff1f; 给定机器为 单台2CPU2G内存。不得使用现成的容器#xff0c;比如map等。 给你一个文件里面包含全国人民14亿的年龄数据0~180现在要你统计每一个年龄 有多少人 给定机器为 单台2CPU2G内存。不得使用现成的容器比如map等。这一句可以忽略 在以上情况下你该如何以最高效的方法来解决这个问题 试想下应该用什么 排序太耗内存考虑时间复杂度同时排序算法最高复杂度为Onlogn 分布式例如hadoop的MapReduce的切开--大题小作没必要 答 可以用数组。开篇引题 实例代码
package algorithm.array;import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStreamReader;
import java.io.UnsupportedEncodingException;import javax.imageio.stream.FileImageInputStream;public class AgeStas {public static void main(String[] args) throws Exception {String str null;String fileName E:\\javacode\\Array\\age1.txt;InputStreamReader isr new InputStreamReader(new FileInputStream(fileName),UTF-8);long start System.currentTimeMillis();BufferedReader br new BufferedReader(isr);int tot 0 ; //21亿int data [] new int[200];while((str br.readLine()) ! null){ //一行一行的读 O(n)int age Integer.valueOf(str);data[age] ;tot ;}//O(n) 14亿. 100万/秒 *1000 10亿 100~1000s之间 500s以下 60*8480sSystem.out.println(总共的数据大小: tot);for(int i 0 ; i 200 ; i ){//下标从0开始的System.out.println(i : data[i]);}//144239ms 144sSystem.out.println(计算花费的时间为: (System.currentTimeMillis() - start) ms);}
}核心思想 通过流的形式一行一行的读然后通过数组下标进行年龄各自累加。同时运行时间和电脑性能也有影响哦。一般100多秒差不多 那么为什么使用数组呢 下标数组最优一个特点。这里可以通下标表示成有意义的数据不只是数据里面的标记年龄和下标对应。 随机访问可以直接通过下标定位到数组中的某一个数据 二 数组 1.定义 所谓数组是有序的元素序列。 若将有限个类型相同的变量的集合命名那么这个名称为数组名。组成数组的各个变量称为数组的分量也称为数组的元素有时也称为下标变量。用于区分数组的各个元素的数字编号称为下标。数组是在程序设计中为了处理方便 把具有相同类型的若干元素按无序的形式组织起来的一种形式。这些无序排列的同类数据元素的集合称为数组。int 的数组你就不能存float 也不能存double 数组是用于储存多个相同类型数据的集合。通常用Array表示也称之为线性表 2. 特点 (1)数组是相同数据类型的元素的集合。 (2)数组中的各元素的存储是有先后顺序的它们在内存中按照这个先后顺序连续存放在一起。内存地址 (3)数组元素用整个数组的名字和它自己在数组中的顺序位置来表示。例如a[0]表示名字为a的数组中的第一个元素a[1]代表数组a的第二个元素以此类推。 4数组是连续的内存空间和相同类型的数据。正是因为这两个限制它才有了一个非常重要的特性随机访问。但有利就有弊这两个限制也让数组的很多操作变得非常低效比如要想在数组中删除、插入一个数据为了保证连续性就需要做大量的数据搬移工作。 随机访问的重要应用查找面试重点 3.缺点 缺点就是数组的插入与删除了具体等会看数组代码时间复杂度都是On.如果将一个数据插入到数组中的第k个位置那么需要将k位置之后的所有数据后移。删除第N个位置的数据那就需要将N后面的所有元素前移一位刚好与插入相反。 4.数组代码实现crud扩容
package Array;/*** author:Kevin* create: 2023-08-12 11:06* Description:*/public class Arraytest {private int size; //数组的长度private int data[];private int index; //当前已经存的数据大小public Arraytest(int size){ //数组的初始化过程this.size size;data new int[size]; //分配的内存空间{0,0,0,0,0}index 0;}public void print(){System.out.println(index: index);for(int i 0 ; i size ; i){System.out.print(data[i] );}System.out.println();}public void insert(int loc,int n){ //时间复杂度 O(n);//TODO 这里判断需不需要扩容,如果插入的元素位置够的话就不需要扩容if(index size){for(int i size - 1; i loc ; i --){ //为什么不能写size 0~size-1 如果loc是0 O(n),O(1)O(n)data[i] data[i - 1]; //把数据往后移一个}data[loc] n;}else {// 进行扩容操作int[] newData new int[size * 2];for (int i 0; i loc; i) {newData[i] data[i];}newData[loc] n;for (int i loc; i size; i) {//这里注意之所以是data[i]是因为数组下标从0开始所以data[i]为插入元素的后一位newData[i 1] data[i];}data newData;size size * 2;index;}}public void delete(int loc){ //O(n)for(int i loc ; i size ; i){if(i ! size - 1){ //怕越界所以加一个判断data[i] data[i 1];}else{data[i] 0; //默认为0 就是没存数据的}}index -- ;}public void update(int loc,int n){//O(1)data[loc] n;}public int get(int loc){ //O(1)return data[loc];}public static void main(String[] args) {//ArrayListArraytest arraytest new Arraytest(6);arraytest.insert(3,5);arraytest.print();}}三数组与A怎么选择 本质是一样的都是数组。ArrayList是JDK封装了。不需要管扩容等操作 数组的话就要你全部操作 两者之间应该如何选用不知道数据大小的肯定选ArrayList。 如果你知道数据的大小而且你又非常关注性能那就用数组。 数组最需要注意的就是越界所以一定要多加判断尤其是在开始和结束。测试的时候也一样注意头和尾。 所以对于开篇的那道算法题可以使用数组 四 数组内存计算 一维 a[] new int[10]; loc init_loc(初始内存地址)index(数组的下标)*size(数据的长度) 二维可以将二维转化为一维 1 2 3 4 5 6 》123456 》4的下标在二维里面是 1 0 在一维里面是第3个。 所以转化为一维的公式为 i*n(一维的长度)j列 》1*303 二维地址公式locinit_loc(i*nj)*size
