Leetcode数组类题目总结(Java版本-20193)

Leetcode151题目详解1 第一章线性表此类题目考察线性表的操作，例如数组，单链表，双向链表1.1 Remove Duplicates from Sorted Array描述Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.Do not allocate extra space for another array, you must do this in place with constant memory.For example, Given input array A = 1,1,2,Your function should return length = 2, and A is now 1,2.分析无代码：public class Solution public int removeDuplicates(int A) if(A=null|A.length=0) return 0; int index=0; for(int i=1;i<A.length;i+) if(Aindex!=Ai) A+index=Ai; return index+1;/爱辅助网：www.aifuzhu.top 相关题：Remove Duplicates from Sorted Array II 见1.21.2 Remove Duplicates from Sorted Array II 描述Follow up for ”Remove Duplicates”: What if duplicates are allowed at most twice?For example, Given sorted array A = 1,1,1,2,2,3,Your function should return length = 5, and A is now 1,1,2,2,3分析可以加一个变量来记录重复元素的个数能很好的解决问题。由于此题已经是排序的了，如果是没有排序的，可以使用hashmap来求元素的个数。代码public class Solution public int removeDuplicates(int A) if(A=null|A.length=0) return 0; int index=0,cnt=0; for(int i=1;i<A.length;i+) if(Aindex!=Ai) A+index=Ai; cnt=0; else if(Aindex=Ai&&cnt<1) A+index=Ai; cnt+; return index+1; 相关题扩展该题到可重复n次的场景，只需要将cnt的上限设为<n-1即可。1.3 Search in Rotated Sorted Array描述Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).You are given a target value to search. If found in the array return its index, otherwise return -1.You may assume no duplicate exists in the array.分析二分查找，此题要特别注意边界值。此题的边界比较多。（1） mid的位置判定，mid可能在左边区域，也可能在右边区域，需求通过（Amid与Afirst大小关系进行判定）（2） 在判定边界时，要注意考虑大于，小于，等于三种情况，在写代码时，本题我开始忘记了一个等号，如代码中标红的地方。（3） 二分的思想是一步一步将区域缩小，并且要充分考虑缩小的正确性，不能放松对边界的警惕（即要注意等于的情况）。如图所示：FirstmidlastFirstmidlast要注意mid落在哪个区域，通过Amid与Afirst大小比较可以确定，同时要注意边界条件的判断，当Amid=Afirst应该是将其归类Amid>Afirst的情况。代码public int search(int A, int target) if(A=null|A.length=0) return -1; int first=0,last=A.length-1; while(first<=last) int mid=(first+last)/2; if(Amid=target) return mid; else if(Amid>=Afirst) if(target>=Afirst&&target<Amid) last=mid-1; else first=mid+1; else if(target>Amid&&target<=Alast) first=mid+1; else last=mid-1; return -1; 相关题目Search in Rotated Sorted Array II，见 §1.41.4 Search in Rotated Sorted Array II描述Follow up for ”Search in Rotated Sorted Array”: What if duplicates are allowed?Would this affect the run-time complexity? How and why?Write a function to determine if a given target is in the array.分析问题就出在边界上，即Amid=Afirst的情况，如果这样，那么无法确定mid的位置属于上题的图一还是图二。因此这时判断Afirst=target,如果不成立则first+缩小一个范围。代码public class Solution public boolean search(int A, int target) if(A=null|A.length=0) return false; int first=0,last=A.length-1; while(first<=last) int mid=(first+last)/2; if(Amid=target) return true; else if(Amid>Afirst) if(target>=Afirst&&target<Amid) last=mid-1; else first=mid+1; else if(Amid<Afirst) if(target>Amid&&target<=Alast) first=mid+1; else last=mid-1; else if(Afirst=target) return true; else first+; return false; 相关题目1.3 Search in Rotated Sorted Array1.5 Median of Two Sorted Arrays描述There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log(m + n).分析看到本题对算法的复杂度要求非常的高，是对数级别的，因此一定要运用二分查找的思想才行。本题更通用的问法是求第k个数。现在需要我们求的是中位数即第（m+n）/2个数。但也不完全准确，如果数组的个数是奇数，那么应该是（m+n）/2,如果是偶数，那么是(m+n)/2+(m+n)/2+1)/2.现在问题转换成了求第K+1个数。（此处的K从1开始计算），从1开始是为了方便。思路是两个数组都查找弟k/2个数，如果Ak/2=Bk/2 return Ak/2Ak/2>Bk/2 递归找k-k/2个数，且b的start位置为k/2+1Ak/2<Bk/2 同样递归找k-k/2,且a的start位置为k/2+1同时要注意如果两个数组长度悬殊太大，那么段数组可能不存在第k/2个元素，因此这是的K为short.length。此题的边界条件判断比较繁琐，当k=1时还需要单独判断，这个在考虑的时候没考虑到是在用例测试的时候发现的问题。代码public class Solution public double findMedianSortedArrays(int A, int B) int lena=A.length; int lenb=B.length; int len=lena+lenb; if(len%2=0)