数组是存放在连续内存空间上的相同类型的集合。
1 - 二分查找
二分查找
二分查找
二分查找
1.给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
思路：
二分查找，注意边界问题，使用左闭右开或者左闭右闭。 在while寻找中每次的边界处理都要根据区间的定义操作。
我习惯使用 左闭右闭 区间的思路。
public int search(int[] nums, int target) {
if (nums == null || nums[0] > target || nums[nums.length - 1] < target) {
return -1;
}
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
2.给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
思路：
方法一：
直接遍历判断，变量index赋值为-1，
如果小于target，记录index，如果等于直接返回，如果大于target直接退出循环。
public int searchInsert(int[] nums, int target) {
if (nums == null) {
return -1;
}
int index = -1;
for (int i = 0; i < nums.length; i++) {
if (nums[i] < target) {
index = i;
} else if (nums[i] == target) {
return i;
} else {
break;
}
}
return index == -1 ? 0 : index + 1;
}
方法二：
二分查找，采用左闭右闭区间。
public int searchInsert(int[] nums, int target) {
if (nums == null) {
return -1;
}
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
3.在排序数组中查找元素的第一个和最后一个位置
public int[] searchRange(int[] nums, int target) {
if (nums == null || nums.length == 0 || nums[0] > target || nums[nums.length - 1] < target) {
return new int[]{-1, -1};
}
int left = 0;
int right = nums.length - 1;
int start = -1, end = -1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
if (left == right) {
return new int[]{mid, mid};
} else {
for (int i = mid; i >= left; i--) {
if (nums[i] == target) {
start = i;
}
}
for (int i = mid; i <= right; i++) {
if (nums[i] == target) {
end = i;
}
}
return new int[]{start, end};
}
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return new int[]{-1, -1};
}
2 - 移除元素
移除元素
移除元素
移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
思路： 可以使用暴力的双层循环解决，外层循环查找是否等于val值，相等时内层for循环为数值向后移动。
另一种方法是使用一层for循环，使用双指针。
- 右指针指向当前将要处理的元素
- 左指针left指向下一个将要赋值的位置
- 如果右指针指向的元素不等于val，一定是数组的一个元素，我们就将右指针指向的元素复制 到左指针位置，然后将左右指针同时右移
- 如果右指针指向的元素等于val，那么不能在输出的数组里，这时候左指针不动，右指针向右移动一位
public int removeElement(int[] nums, int val) {
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}