《Leetcode数组类题目总结(Java版本-20193)》由会员分享，可在线阅读，更多相关《Leetcode数组类题目总结(Java版本-20193)（39页珍藏版）》请在金锄头文库上搜索。
1、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 memo
2、ry.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;iA.length;i+) if(Aindex!=Ai) A+index=Ai; return index+1;/爱辅助网：www.aifuzhu.top 相
3、关题：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分析可以加一个变量来记录重复元素的个数
4、能很好的解决问题。由于此题已经是排序的了，如果是没有排序的，可以使用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;iA.length;i+) if(Aindex!=Ai) A+index=Ai; cnt=0; else if(Aindex=Ai&cnt1) A+index=Ai; cnt+; return index+1; 相关题扩展该题到可重复n次的场景，只需要将cn
5、t的上限设为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=Afirst) if(target=Afirst&targetAmid&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
6、描述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+缩小一个范围。代码pub
7、lic 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(firstAfirst) if(target=Afirst&targetAmid) last=mid-1; else first=mid+1; else if(AmidAmid&targetBk/2 递归找k-k/2个数，且b的start位置为k/2+1Ak/2Bk/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)
