Java 数组
Scintillator. / 人气:01、数组理论基础
数组是存放在连续内存空间上的相同类型数据的集合，可以通过下标索引的方式获取到下标下对应的数据。
举个栗子（字符数组）~
可以看到：
1、数组的下标从0开始
2、数组在内存中的地址是连续的
所以在删除元素时，只能用覆盖的方式进行。
例如，要删除下标为2的元素~ 就需要将从2之后的元素依次移到前一个，覆盖掉要删除的元素。
所以删除元素并不是将该元素的空间释放了，而是将后面的元素移到前面，覆盖掉要删除的元素，然后将数组的长度减去1，就能得到一个看似新的数组。
在java中，二维数组的存储方式如下：
2、常见考点
1.二分查找
力扣题目链接: 二分查找
这道题目的前提是有序数组，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件。
二分查找思想是：
数组有序的前提下（假设升序），如果数组中间的值大于要查找的值，那么要查找的元素就不可能在后半部分，因为后半部分的值都大于中间的值，所以通过第一次比较，就可以将范围缩小一半，后面同理，即时间复杂度降到了O(logN)，效率大大提高，当题目中要求查找元素的时间复杂度为O(logN)时，首先想一想是否能用二分呢？
class Solution {
public int search(int[] nums, int target) {
// 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
if (target < nums[0] || target > nums[nums.length - 1]) {
return -1;
}
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid - 1;
}
return -1;
}
}
2.移除元素
有的同学可能说了，多余的元素，删掉不就得了？但是要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。
例如：给你一个数组和一个val值，要求删除数组中等于val值的元素，怎么做呢？
思路1：暴力法
我们可以使用两个for循环，当遍历到等于val值的元素时，就将后面的元素整体往前移一个覆盖掉要删除的元素，但是这种做法显然时间复杂度太高。
class Solution {
public int removeElement(int[] nums, int val) {
int size = nums.length;
for (int i = 0; i < size;i++ ) {
if (nums[i] == val) { // 发现需要移除的元素，就将数组后面集体向前移动一位
for (int j = i + 1; j < size; j++) {
nums[j - 1] = nums[j];
}
i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
size--;
}
}
return size;
}
}
思路2：双指针法
分别设设一个快慢指针，slow fast ，两者一起走，当慢指针遇到要删除的元素时停下，等待着被删除（覆盖）；当快指针走到要被留下的元素时，将快指针的元素赋值给慢指针，然后两指针同时向后走，直到快指针遍历完整个数组。
可以这么理解：定义数组的新长度newLength ，从0开始，定义一个快指针遍历数组 fast，当fast走到要被留下的元素时，说明该元素应该被添加到新数组中（即被添加到newLength 下标，这里相当于 newLength 之前的部分数组看做要返回的新数组，相当于往这个新数组里插入元素）。
class Solution {
public int removeElement(int[] nums, int val) {
int fast = 0;// 定义一个快指针遍历数组
int newLength = 0;// 定义新的数组长度
while(fast < nums.length){
if(nums[fast] != val){
nums[newLength++] = nums[fast];
}
fast++;
}
return newLength;
}
}
推荐力扣题目
其他常见数组的考点很多都是以这两点为基础，无非就是对数组增删改查，将数组的查找和删除掌握了，就可以开始刷题啦。
加载全部内容