- 所谓数组，是有序的元素序列。若将有限个类型相同的变量的集合命名，那么这个名称为数组名。组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。用于区分数组的各个元素的数字编号称为下标。数组是在程序设计中，为了处理方便，把具有相同类型的若干元素按无序的形式组织起来的一种形式。
1 搜索二维数组
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：每行中的整数从左到右按升序排列。每行的第一个整数大于前一行的最后一个整数。示例 1:输入:matrix = [[1, 3, 5, 7],[10, 11, 16, 20],[23, 30, 34, 50]]target = 3输出: true
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
if(m == 0) return false;
int n = matrix[0].length;
int lo =0, hi = m*n-1;
while(hi >= lo){
int mid = (hi+lo)/2;
int r = mid/n;
int l = mid%n;
if(matrix[r][l] == target){
return true;
}
else if(matrix[r][l] > target){
hi = mid-1;
}
else{
lo = mid+1;
}
}
return false;
}
}
2搜索二维矩阵 II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
- idea: 先从第一行最后一列开始， 比target小就row++， 比target小 cl—、else return true；
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix == null || matrix.length < 1 || matrix[0].length <1 ){
return false;
}
int cl = matrix[0].length-1;
int len =matrix.length;
int row = 0;
while(row< len && cl >=0){
if(matrix[row][cl] < target ){
row++;
}
else if( matrix[row][cl] > target){
cl--;
}
else{
return true;
}
}
return false;
}
}
3 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
class Solution {
private int extremeInsertionIndex(int[] nums, int target, boolean left) {
int lo = 0;
int hi = nums.length;
while (lo < hi) {
int mid = (lo+hi)/2;
if((nums[mid] > target) || (left && nums[mid] == target) ){
hi = mid;
}
else if((nums[mid] < target) || (!left && nums[mid] == target) ){
lo = mid+1;
}
}
return lo;
}
public int[] searchRange(int[] nums, int target) {
int[] targetRange = {-1, -1};
int leftIdx = extremeInsertionIndex(nums, target, true);
// assert that `leftIdx` is within the array bounds and that `target`
// is actually in `nums`.
if(leftIdx ==nums.length || nums[leftIdx] != target){
return targetRange;
}
targetRange[0] = leftIdx;
targetRange[1] = extremeInsertionIndex(nums, target, false)-1;
return targetRange;
}
}
4最长连续递增序列
给定一个未经排序的整数数组，找到最长且连续的的递增序列。
示例 1:
输入: [1,3,5,4,7]
输出: 3
解释: 最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为5和7在原数组里被4隔开。
- idea: 当i= 0的时候 , i>0;
class Solution {
public int findLengthOfLCIS(int[] nums) {
int ans = 0, anchor = 0;
for (int i = 0; i < nums.length; ++i) {
if (i > 0 && nums[i-1] >= nums[i]) anchor = i;
ans = Math.max(ans, i - anchor + 1);
}
return ans;
}
}
5 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
- idea: ans 保存以前的最大值， sum代表当前节点的最大值， 动态更新ans;
class Solution {
public int maxSubArray(int[] nums) {
int len = nums.length;
int sum = 0;
int ans = nums[0];
for(int i =0; i<len; i++){
if(sum > 0){
sum +=nums[i];
}else{
sum = nums[i];
}
ans = Math.max(sum, ans);
}
return ans;
}
}
6 汇总区间
给定一个无重复元素的有序整数数组，返回数组区间范围的汇总。
示例 1:
输入: [0,1,2,4,5,7]
输出: [“0->2”,”4->5”,”7”]
解释: 0,1,2 可组成一个连续的区间; 4,5 可组成一个连续的区间。
- idea: 双指针 用 i表示开始节点， j表示结束节点，
- j++ 时的条件，j+1小于数组的长度, nums[j]+ 1 == nums[j+1]
- j==i时， 同一个节点，
- 更新i时， 用j+1,
public class Solution {
public List<String> summaryRanges(int[] nums) {
List<String> summary = new ArrayList<>();
for (int i = 0, j = 0; j < nums.length; ++j) {
// check if j + 1 extends the range [nums[i], nums[j]]
if (j + 1 < nums.length && nums[j + 1] == nums[j] + 1)
continue;
// put the range [nums[i], nums[j]] into the list
if (i == j)
summary.add(nums[i] + "");
else
summary.add(nums[i] + "->" + nums[j]);
i = j + 1;
}
return summary;
}
}
7按奇偶排序数组
给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素。
你可以返回满足此条件的任何数组作为答案。
输入：[3,1,2,4]
输出：[2,4,3,1]
输出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也会被接受。
- idea: 双指针 lo 偶数指针， hi奇数指针。 while( lo < hi) 动态更新lo， hi。
类型题
- 可以被3整除， 与不可以的。
class Solution {
public int[] sortArrayByParity(int[] A) {
int len =A.length;
int[] B = new int[len];
int index = 0;
int lenB = len-1;
for(int i = 0; i<len; i++){
if(A[i] % 2 == 0){
B[index++] = A[i];
}
else{
B[lenB--] = A[i];
}
}
return B;
}
}
8 嵌套的数组
索引从0开始长度为N的数组A，包含0到N - 1的所有整数。找到并返回最大的集合S，S[i] = {A[i], A[A[i]], A[A[A[i]]], ... }且遵守以下的规则。
假设选择索引为i的元素A[i]为S的第一个元素，S的下一个元素应该是A[A[i]]，之后是A[A[A[i]]]... 以此类推，不断添加直到S出现重复的元素。
示例 1:
输入: A = [5,4,0,3,1,6,2]
输出: 4
解释:
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
其中一种最长的 S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}
- idea: 双重循环，
class Solution { public int arrayNesting(int[] nums) { int len = nums.length; int max=0; for(int i =0; i<len; i++){ int count = 0; int j = i; while(nums[j] != -1){ count++; int t = nums[j]; nums[j] = -1; j = t; } max= Math.max(max, count); } return max; } }
9 颜色分类
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
class Solution {
public void sortColors(int[] nums) {
int len = nums.length-1;
int lo = 0, i = lo;
while(i <= len){
if(nums[i] < 1){
swap(nums,i++, lo++);
}
else if(nums[i] > 1){
swap(nums, i, len--);
}
else{
i++;
}
}
}
private void swap(int[]nums, int i , int j){
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
10 删除排序数组中的重复项 II
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定 nums = [1,1,1,2,2,3],
函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。
你不需要考虑数组中超出新长度后面的元素。
class Solution {
public int removeDuplicates(int[] nums) {
int j = 0;
for(int i = 0; i<nums.length; i++){
if( j <2 || nums[i]>nums[j-2] ){
nums[j++] = nums[i];
}
}
return i;
}
}
11 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
多种解法， 位运算， hash表等等 ```java class Solution { public int singleNumber(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<>(); for(Integer s: nums){ Integer count = map.get(s); count = count == null ? 1 : ++count; map.put(s, count); } for(Integer i : map.keySet()){ Integer count = map.get(i); if(count ==1){ return i; } } return 0;} }
// 位运算 class Solution { public int singleNumber(int[] nums) { int len = nums.length; if(len == 1) return nums[0]; int ans = nums[0]; for(int i = 1; i<len; i++){ ans ^=nums[i]; } return ans; } }
<a name="LrzK1"></a>
### 12 [两数之和](https://leetcode-cn.com/problems/two-sum/)
给定一个整数数组 `nums` 和一个目标值 `target`，请你在该数组中找出和为目标值的那 **两个** 整数，并返回他们的数组下标。<br />你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。<br />**示例:**<br />给定 nums = [2, 7, 11, 15], target = 9
因为 nums[**0**] + nums[**1**] = 2 + 7 = 9<br />所以返回 [**0, 1**]
- hashmap，
```java
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i<nums.length; i++){
int com = target - nums[i];
if(map.containsKey(com)){
return new int[]{map.get(com), i};
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No");
}
}
13 面试题21. 调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
示例：
输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。
负数在正数前面
能被3整除的数都在不能被3整除的数前面
class Solution {
public int[] exchange(int[] nums) {
int hi = nums.length-1, lo = 0;
while(hi>lo){
while(hi>lo && (nums[lo]%2 != 0) ){
lo++;
}
while(hi>lo && (nums[hi]%2 == 0)){
hi--;
}
if(hi>lo){
int temp = nums[hi];
nums[hi] = nums[lo];
nums[lo] = temp;
}
}
return nums;
}
}
class Solution {
public int[] exchange(int[] nums) {
int hi = nums.length-1, lo = 0;
while(hi>lo){
while(hi>lo && !isEven(nums[lo]) ){
lo++;
}
while(hi>lo && isEven(nums[hi]) ){
hi--;
}
if(hi > lo){
int temp = nums[hi];
nums[hi] = nums[lo];
nums[lo] = temp;
}
}
return nums;
}
boolean isEven(int n){
return (n&1 ) == 0;
}
}
若有收获，就点个赞吧
0 人点赞
