算法通关村第三关—数组基本操作(青铜)

本文主要是介绍算法通关村第三关—数组基本操作(青铜)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

数组基本操作

一、数组的创建和初始化

创建

int[] arr = new int[10];

初始化

int[] arr = new int[]{0,1,2,3}
int[] arr = {0,1,2,3}

二、增加一个元素

将给定的元素插入到有序数组的对应位置中，我们可以先找位置，再将其后元素整体右移，最后插入到空位置上。这里需要注意，算法必须能保证在数组的首部、尾部和中间位置插入都可以成功。该问题貌似个for循环就搞定了，但是如果面试直接让你写并能正确运行，我相信很多人还是会折腾很久，甚至直接会挂。因为自己写的时候会发现游标写size还是size-1,判断时要不要加等于等等，这里推荐一种实现方式。

/***dparam arr*dparam size*数组已经存储的元素数量，从1开始编号*@param element待插入的元素*return*/
public static int addByElementSequence(int[]arr,int size,int element){//问题①：是否应该是size>arr.lengthif (size > arr.length) retrun -1;//问题②想想这里是否是index=0或者size-1?int index = size;//找到新元素的插入位置，问题③这里是否应该是size-1?for (int i = 0;i < size;i++){if (element < arr[i]){index = i;break;}//元素后移，问题④想想这里为什么不是s1ze-1for (int j = size; j > index; j--){arr[j] = arr[j-i];//index下标开始的元素后移一个位置}arr[index] = element;//插入数据return index;}

三、删除一个元素

对于删除，要分为两个步骤，先从最左侧开始查是否存在元素，如果元素存在，则从该位置开始执行删除操作。
例如序列是1 2 3 4 5 6 7 8 9，要删除5，则应先遍历，找到5，然后从5开始执行删除操作，也就是从6开始逐步覆盖上一个元素，最终将序列变成1 2 3 4 6 7 8 9 [9]。
这个方法和增加元素一样，必须自己亲自写才有作用，该方法同样要求删除序列最前、中间、最后和不存在的元素都能有效，下面给一个参考实现：

/***从数组中删除元素key*@param arr数组*@param size数组中的元素个数，从1开始*@param key删除的目标值*/
public int removeByElement(int[]arr,int size,int key){int index = -1;for(int i = 0; i < size; i++){if (arr[i] = key){index = i;break;}}if（index != -1){for (int i = index + 1; i < size; i++)arr[i-1] = arr[i];size--;}return size;
}

四、算法热身-单调序列

先看个热身问题，我们在写算法的时候，数组是否有序是一个非常重要的前提，有或者没有可能会采用完全不同的策略。LeetCode896.判断一个给定的数组是否为单调数组。
分析：如果对于所有i<=j,A[i]<=A[j],那么数组A是单调递增的。如果对于所有i<=j,A[i>=A[j],那么数组A是单调递减的。所以遍历数组执行这个判定条件就行了，由于有递增和递减两种情况。
于是我们执行两次循环就可以了，代码如下：

//这里用i和j的长度判断是否整个数组都是单调的
class Solution {public boolean isMonotonic(int[] nums) {if(nums.length <= 2) return true;int i = 1;while(i < nums.length){if(nums[i] > nums[i - 1]) break;i++;}int j = 1;while(j < nums.length){if(nums[j] < nums[j - 1]) break;j++;}return i == nums.length || j == nums.length;}
}

老师的改进方法，变成一次循环

public boolean isMonotonic(int[] nums){boolean inc true, dec true;int n = nums.length;for(int i = 0; i < n-1; ++i){if (nums[i] > nums[i + 1]){inc = false;}if (nums[i] < nums[i + 1]){dec = false;}}return inc || dec;
}

我们判断整体单调性不是白干的，很多时候需要将特定元素插入到有序序列中，并保证插入后的序列仍然有序，例如leetcodes35：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
这个问题没有让你将新元素插入到原始序列中，还是比较简单的，只要遍历一下就找到了。如果面试官再问你，该如何更快的找到目标元素呢？那他其实是想考你二分查找。以后凡是提到在单调序列中查找的情况，我们应该马上想到是否能用二分来提高查找效率。这里只看一下实现代码：

public int searchInsert(int[]nums,int target){int n = nums.Length;int left = 0, right = n-1,ans = n;while (left <= right){int mid = ((right -left)>>1) + left;if (target <= nums.[mid]){ans = mid;right = mid - 1;}else left = mid + 1;}
}
return ans;
}

五、算法热身-数组合并专题

数组合并就是将两个或者多个有序数组合并成一个新的。这个问题的本身不算难，但是要写的够出彩才可以。还有后面要学的归并排序本身就是多个小数组的合并，所以研究该问题也是为了后面打下基础。
先来看如何合并两个有序数组，LeetCode88：给你两个按非递减顺序排列的整数数组nums1和nums2,另有两个整数m和n,分别表示nums1和nums2中的元素数目。请你合并nums2到nums1中，使合并后的数组同样按非递减顺序排列。
注意：最终合并后数组不应由函数返回，而是存储在数组nums1中。为了应对这种情况，nums1的初始长度为m+n,其中前m个元素表示应合并的元素，后n个元素为0应忽略。nums2的长度为n。

思路一：把数组2插入到数组1后面，然后对数组1排序

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {for(int i = m; i < m + n; i++){nums1[i] = nums2[i - m];}Arrays.sort(nums1);}
}

但是这么写只是为了开拓思路，面试官会不喜欢，太没技术含量了。这个问题的关键是将B合并到A的仍然要保证有序。因为A是数组不能强行插入，如果从前向后插入，数组A后面的元素会多次移动，代价比较高。此时可以借助一个新数组C来做，先将选择好的放入到C中，最后再返回。这样虽然解决问题了，但是
面试官可能会问你能否再优化一下，或者不申请新数组就能做呢？更专业的问法是：上面算法的空间复杂度为0(n),能否有0(1)的方法？
思路二
比较好的方式是从后向前插入，A和B的元素数量是固定的，所以排序后最远位置一定是A和B元素都最大的那个，依次类推，每次都找最大的那个从后向前填就可以了，代码如下：

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int len = m + n - 1,len1 = m - 1, len2 = n -1;while(len1 >= 0 && len2 >= 0){if(nums1[len1] > nums2[len2]){nums1[len] = nums1[len1];len1--;}else{nums1[len] = nums2[len2];len2--;}len--;}//假如两个数组还有剩余while(len1  >= 0){nums1[len] = nums1[len1];len1--;len--;}while(len2 >= 0){nums1[len] = nums2[len2];len2--;len--;}}
}