目录
数组是存放在连续内存空间上的相同类型数据的集合。
有关数组其他的性质欢迎访问:https://www.cnblogs.com/zwtblog/p/15056076.html#线性表的顺序表示
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示:
这道题目的前提是数组为有序数组,同时题目还强调数组中无重复元素
这些都是使用二分法的前提条件
例如到底是
while(left < right)
还是while(left <= right)
,到底是right = middle
呢,还是要right = middle - 1
呢?
大主要是因为对区间的定义没有想清楚,区间的定义就是不变量。要在二分查找的过程中,保持不变量,就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作,这就是循环不变量规则。
写二分法,区间的定义一般为两种,左闭右闭即[left, right],或者左闭右开即[left, right)。
定义 target 是在一个在左闭右闭的区间里,也就是[left, right] (这个很重要非常重要)。
int left = 0;
int right = nums.size() - 1;
while (left <= right) 要使用 <= ,因为left == right是有意义的,所以使用 <=
int middle = left + ((right - left) / 2); // 防止溢出 等同于(left + right)/2
if (nums[middle] > target) right 要赋值为 middle - 1,因为当前这个nums[middle]一定不是target,那么接下来要查找的左区间结束下标位置就是 middle - 1
例如在数组:1,2,3,4,7,9,10中查找元素2,如图所示:
代码如下:(详细注释)
// 版本一
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1; // 定义target在左闭右闭的区间里,[left, right]
while (left <= right) { // 当left==right,区间[left, right]依然有效,所以用 <=
int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
if (nums[middle] > target) {
right = middle - 1; // target 在左区间,所以[left, middle - 1]
} else if (nums[middle] < target) {
left = middle + 1; // target 在右区间,所以[middle + 1, right]
} else { // nums[middle] == target
return middle; // 数组中找到目标值,直接返回下标
}
}
// 未找到目标值
return -1;
}
};
如果说定义 target 是在一个在左闭右开的区间里,也就是[left, right) ,那么二分法的边界处理方式则截然不同。
有如下两点:
在数组:1,2,3,4,7,9,10中查找元素2,如图所示:(注意和方法一的区别)
// 版本二
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size(); // 定义target在左闭右开的区间里,即:[left, right)
while (left < right) { // 因为left == right的时候,在[left, right)是无效的空间,所以使用 <
int middle = left + ((right - left) >> 1);
if (nums[middle] > target) {
right = middle; // target 在左区间,在[left, middle)中
} else if (nums[middle] < target) {
left = middle + 1; // target 在右区间,在[middle + 1, right)中
} else { // nums[middle] == target
return middle; // 数组中找到目标值,直接返回下标
}
}
// 未找到目标值
return -1;
}
};
package 数组;
import java.util.Scanner;
public class Main_704 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int target = scanner.nextInt();
int[] nums = new int[6];
for (int i = 0; i < nums.length; i++) {
nums[i] = scanner.nextInt();
}
System.out.println(search(nums, target));
}
private static int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// int mid = (left + right)/2;
if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
return mid;
}
}
return -1;
}
}
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 : 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
你不需要考虑数组中超出新长度后面的元素。
这个题目暴力的解法就是两层for循环,一个for循环遍历数组元素 ,第二个for循环更新数组。
代码如下:
代码如下:
// 时间复杂度:O(n^2)
// 空间复杂度:O(1)
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int size = nums.size();
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--; // 此时数组的大小-1
}
}
return size;
}
};
双指针法(快慢指针法): 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
删除过程如下:
//双指针法(快慢指针法)在数组和链表的操作中是非常常见的,很多考察数组、链表、字符串等操作的面试题,都使用双指针法。
// 时间复杂度:O(n)
// 空间复杂度:O(1)
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slowIndex = 0;
for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
if (val != nums[fastIndex]) {
nums[slowIndex++] = nums[fastIndex];
}
}
return slowIndex;
}
};
int slowIndex = 0
for(fastIndex =0 ,…………)
if(val ! = fast)
package 数组;
import java.util.Scanner;
public class Main_27 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[] nums = new int[8];
for (int i = 0; i < nums.length; i++) {
nums[i] = scanner.nextInt();
}
int val = scanner.nextInt();
System.out.println(removeElement(nums, val));
}
private static int removeElement(int[] nums, int val) {
int slowIndex = 0;
for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
if (val != nums[fastIndex]) {
nums[slowIndex++] = nums[fastIndex];
}
}
return slowIndex;
}
}
给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
示例 : 输入:nums = [-4,-1,0,3,10] 输出:[0,1,9,16,100] 解释:平方后,数组变为 [16,1,0,9,100],排序后,数组变为 [0,1,9,16,100]
最直观的相反,莫过于:每个数平方之后,排个序,美滋滋,代码如下:
class Solution {
public:
vector<int> sortedSquares(vector<int>& A) {
for (int i = 0; i < A.size(); i++) {
A[i] *= A[i];
}
sort(A.begin(), A.end()); // 快速排序
return A;
}
};
这个时间复杂度是 O(n + nlogn), 可以说是O(nlogn)的时间复杂度
数组其实是有序的, 只不过负数平方之后可能成为最大数了。
那么数组平方的最大值就在数组的两端,不是最左边就是最右边,不可能是中间。
此时可以考虑双指针法了,left 指向起始位置,j指向终止位置。
定义一个新数组result,和A数组一样的大小,让k指向result数组终止位置。
如果左平方 < 右平方
那么result[k--] = 右平方;
。
如果左平方 >= 右平方
那么result[k--] = 左平方;
。
如动画所示:
此时的时间复杂度为O(n),相对于暴力排序的解法O(n + nlogn)还是提升不少的。
class Solution {
public int[] sortedSquares(int[] nums) {
int right = nums.length - 1;
int left = 0;
int[] result = new int[nums.length];
int index = result.length - 1;
while (left <= right) {
if (nums[left] * nums[left] > nums[right] * nums[right]) {
result[index--] = nums[left] * nums[left];
++left;
} else {
result[index--] = nums[right] * nums[right];
--right;
}
}
return result;
}
}
给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。
示例:
输入:s = 7, nums = [2,3,1,2,4,3] 输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
这道题目暴力解法当然是 两个for循环,然后不断的寻找符合条件的子序列,时间复杂度很明显是O(n^2)
接下来就开始介绍数组操作中另一个重要的方法:滑动窗口。
所谓滑动窗口,就是不断的调节子序列的起始位置和终止位置,从而得出我们要想的结果。
这里还是以题目中的示例来举例,s=7, 数组是 2,3,1,2,4,3,来看一下查找的过程:
可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况,不断调节子序列的起始位置。从而将O(n^2)的暴力解法降为O(n)。
int minSubArrayLen(int s, vector<int>& nums) {
int result = INT32_MAX;
int sum = 0; // 滑动窗口数值之和
int i = 0; // 滑动窗口起始位置
int subLength = 0; // 滑动窗口的长度
for (int j = 0; j < nums.size(); j++) {
sum += nums[j];
// 注意这里使用while,每次更新 i(起始位置),并不断比较子序列是否符合条件
while (sum >= s) {
subLength = (j - i + 1); // 取子序列的长度
result = result < subLength ? result : subLength;
sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处,不断变更i(子序列的起始位置)
}
}
// 如果result没有被赋值的话,就返回0,说明没有符合条件的子序列
return result == INT32_MAX ? 0 : result;
}
时间复杂度:\(O(n)\)
空间复杂度:\(O(1)\)
不要以为for里放一个while就以为是 O(n^2) , 主要是看每一个元素被操作的次数,每个元素在滑动窗后进来操作一次,出去操作一次,每个元素都是被被操作两次,所以时间复杂度是2 * n 也就是 O(n) 。
给定一个正整数 n,生成一个包含 1 到 n^2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
本题并不涉及到什么算法,就是模拟过程,但却十分考察对代码的掌控能力。
而求解本题依然是要坚持循环不变量原则。
模拟顺时针画矩阵的过程:由外向内一圈一圈这么画下去。
可以发现这里的边界条件非常多,在一个循环中,如此多的边界条件,如果不按照固定规则来遍历,那就是一进循环深似海,从此offer是路人。
public int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
// 循环次数
int loop = n / 2;
// 定义每次循环起始位置
int startX = 0;
int startY = 0;
// 定义偏移量
int offset = 1;
// 定义填充数字
int count = 1;
// 定义中间位置
int mid = n / 2;
while (loop > 0) {
int i = startX;
int j = startY;
// 模拟上侧从左到右
for (; j<startY + n -offset; ++j) {
res[startX][j] = count++;
}
// 模拟右侧从上到下
for (; i<startX + n -offset; ++i) {
res[i][j] = count++;
}
// 模拟下侧从右到左
for (; j > startY; j--) {
res[i][j] = count++;
}
// 模拟左侧从下到上
for (; i > startX; i--) {
res[i][j] = count++;
}
loop--;
startX += 1;
startY += 1;
offset += 2;
}
if (n % 2 == 1) {
res[mid][mid] = count;
}
return res;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章