【Java版数据结构】数组

2022-02-08 10:55:16

一、例题一：2的n次方

判断一个数是否是2的N次方。比如2 4 8 16，是的；6 10 不是的。就看这个数是不是可以拆成N个2相乘。

解法1：

    public static boolean solution1(int x) {
        // 4 6 16 是2的n次方 , 15 不是
        if (x == 0 || x == 1) {
            return true;
        }
        while (x > 1) {
            int i = (x % 2 == 0) ? (x /= 2) : (x = 0);
        }
        if (x == 1) return true;
        return false;
    }

解法2：

若x满足x = 2^{^}n, x&(x-1) == 0

1000

0111

    public static boolean solution2(int x) {
        // 4 6 16 是2的n次方 , 15 不是
        if ((x & (x - 1)) == 0) return true;
        return false;
    }

二、例题二：高效地读文件（面试经典）

给你一个文件里面包含全国人民（14亿）的年龄数据（0~180），现在要你统计每一个年龄有多少人？
**限制：**给定机器为单台+1CPU+1G内存。不得使用现成的容器，比如map等。

分析：假设每个年龄数据为2位数，gbk编码下每个数字字符size = 1B，该文件总大小 = 14*(10^8)*2B /1000 /1000 /1000 = 1.4G ，一次放不下，且使用排序算法的话，排序的最高效算法时间复杂度为：O(nlogn) ，其中n=14亿，排不出来，而且内存也不够。如果使用现成的容器可以直接解决，如不使用现成容器，可以考虑用数组来实现。

解法一：直接思路，分布式存储（例如使用hadoop框架，HDFS存储，使用MapReduce计算后合并），有点蠢

解法二：数组算法
在以上情况下你该如何以最高效的方法来解决这个问题？

int a[] = new int[180];

a[0]++; // 0表示的是0岁，a[0]的值表示的就是0有多少人.

12：56
23：5611
52：9999888

下标：数组最优一个特点。这里可以通下标表示成有意义的数据，不只是数据里面的标记，年龄和下标对应。随机访问：可以直接通过下标定位到数组中的某一个数据(高效查询)

public class AgeStas {

	public static void main(String[] args) throws Exception {
		String str = null;
		String fileName = "D:\\JavaEE软开工程师\\算法刷题\\数据结构与算法\\02 基础数据结构\\age1.txt";
		InputStreamReader isr = new InputStreamReader(new FileInputStream(fileName),"UTF-8");

		long start = System.currentTimeMillis();
		BufferedReader br = new BufferedReader(isr);
		int tot = 0 ;	// 14亿
		// 缓存桶
		int data[] = new int[200];
		while((str = br.readLine()) != null){		//一行一行的读 O(n)
			int age = Integer.valueOf(str);
			data[age] ++ ;
			tot ++ ;
		}
		// O(n) 14亿.
		// 单核Cpu处理速度(考虑了和内存的交互速度): 100万/秒 - 1000万/秒
		// 100s ~ 1000s之间
		// 16核 6s ~ 60s之间
		System.out.println("总共的数据大小: " + tot);
		
		for(int i = 0 ; i < 200 ; i ++){//下标从0开始的
			System.out.println(i + ":" + data[i]);
		}
		// 43757ms => 43s
		System.out.println("计算花费的时间为:" + (System.currentTimeMillis() - start) + "ms");
	}
}

// 输出结果
总共的数据大小: 1400000000
0:7780353
1:7778794
2:7773040
3:7779555
4:7776882
5:7773873
6:7778810
7:7777106
8:7781165
9:7782188
10:7774890
11:7776274
12:7778024
13:7777931
...

三、数组的结构

基本数据结构：[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IoqJuNhV-1635678831610)(D:\JavaEE软开工程师\算法刷题\数据结构与算法\02 基础数据结构-数组\基本数据结构图.jpg)]

1.数组的定义

所谓数组，是有序的元素序列。若将有限个类型相同的变量的集合命名，那么这个名称为数组名。组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。用于区分数组的各个元素的数字编号称为下标。数组是在程序设计中，为了处理方便，把具有相同类型的若干元素按无序的形式组织起来的一种形式。这些无序排列的同类数据元素的集合称为数组。int 的数组你就不能存float 也不能存double

数组是用于储存多个相同类型数据的集合。通常用Array表示，也称之为线性表。

2.特点

(1)数组是相同数据类型的元素的集合。

(2)数组中的各元素的存储是有先后顺序的，它们在内存中按照这个先后顺序连续存放在一起，即内存地址连续。

(3)数组元素用整个数组的名字和它自己在数组中的顺序位置来表示。例如，a[0]表示名字为a的数组中的第一个元素，a[1]代表数组a的第二个元素，以此类推。

3.表现形式

（1）一维数组

Int a[],String a[]

（2）多维数组

Int a[][],int a[][][]。 int a[m][n]:内存空间是多少？ m*n*typeSize

a[0][10]: 链表解决，a[0]:->10>2 a[1]->15

4.随机访问：

数组是连续的内存空间和相同类型的数据。正是因为这两个限制，它才有了一个非常重要的特性：随机访问。但有利就有弊，这两个限制也让数组的很多操作变得非常低效，比如要想在数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。

随机访问的重要应用：查找，面试重点， O(1)

5.数组的缺点：插入和删除

O(n)

实现代码：

设数组的长度为n，现在，如果我们需要将一个数据插入到数组中的第k个位置。删除第N个位置的数据.

github链接: [代码待上传]

6.使用数组一定要注意访问越界问题。

7.思考：为什么很多计算机编程语言中数组的下标要从0开始呢？

定义一个数组一定会分配内存空间。数组的特点是：内存是一段连续的地址。

int a[] = new int[3];

到内存中申请空间：10001,10002,10003

存数据

a[0] => 10001 ====> 10001+0*typesize

a[1] => 10002 =====> 10001+1*typesize

a[2]=> 10003 =====> 10001+2*typesize

如果我们不从0开始，会浪费cpu计算量

a[1] = 10001+(1-1)

a[2] = 10001+(2-1)

a[3] = 10001+(3-1)

四、ArrayList和数组的比较

本质是一样的，都是数组。ArrayList是JDK封装了。不需要管扩容等操作

数组的话就要你全部操作

两者之间应该如何选用？：

不知道数据大小的肯定选ArrayList。

如果你知道数据的大小而且你又非常关注性能那就用数组。

数组最需要注意的就是越界：所以一定要多加判断，尤其是在开始和结束。测试的时候也一样注意头和尾。

五、jvm内存

Java里面的内存分为几种？

Java分为堆栈两种内存。

什么是堆内存？：存放new创建的对象和数组（凡是new出来的都在堆内存里）

什么是栈内存？引用变量

堆栈都用Java用来存放数据的地方，与C++ / c不一样。java自动管理我们的堆栈。Gc（主要回收堆内存），new出来的你没管过。

堆栈的区别：

1.栈的速度要快

2.栈内存的数据可以共享(缓存)，主要存一些基本数据类型。

int a = 3; //在栈中创建变量a 然后给a赋值，先不会创建一个3而是先在栈中找有没有3，如果有直接指向。如果没有就加一个3进来。

int b =3; //首先也要创建一个变量b，把a处创建的3复用进来

六、例题三：String（面试经典）


String str1 = "abc"; String str2 = "abc"; System.out.println(str1==str2);	//true


String str1 = "abc"; String str2 = "abc"; str1 = "bcd"; 
System.out.println(str1 + "," + str2); 	//bcd,abc
System.out.println(str1==str2); 		//false 虽然最开始 str1和str2都指向同一个变量abc但str1引用变化后不会改变str2的

String str1 = "abc"; 
String str2 = "abc"; 
str1 = "bcd"; 
String str3 = str1;  //abc
System.out.println(str3);  //bcd
String str4 = "bcd"; 
System.out.println(str1 == str4);	//true

String str1 = new String("abc"); 
String str2 = "abc"; 
System.out.println(str1==str2); 	//false  new在堆内存中新开了一个对象

String s1 = "ja";
String s2 = "va";
String s3 = "java";
String s4 = s1 + s2; //java 注意这个+号，java里面重载了+，其实调用了stringBuild，会new对象。
System.out.println(s3 == s4);	//false
System.out.println(s3.equals(s4;	//true 只是比较值
))

拓展：二维数组的内存地址是怎么样的？写出寻址公式

a[2][3]

a[0][0] => 10000 ====> 10000+0 * typesize

a[0][1] => 10004 =====> 10000 +1 * typesize

a[0][2] => 10008 =====> 10000 +2 * typesize

a[1][0] => 10012 =====> 10000 +(1*3 + 0) * typesize

a[1][1] => 10016 =====> 10000 +(1*3 + 1) * typesize

a[1][2] => 10020 =====> 10000 +(1*3 + 2) * typesize

总结

数组是一个最基础最简单的数据结构，必须要完全搞懂。它是存储相同类型的一组数据，最大的两个特点就是

下标和随机访问。缺点就是插入和删除是很慢的，时间复杂度为O（n）。

码农公寓