参考刷题顺序: 力扣刷题顺序
涉及题目
自己的想法:
刚开始想的是利用list的indexOf方法,来查找丢失的和重复的。但是花费的时间太多。首先对数组进行排序,如果前后相等,则是重复,如果前后间隔为2,则是缺少。
class Solution {
public int[] findErrorNums(int[] nums) {
int n=nums.length;
int[] result = new int[2];
Arrays.sort(nums);
if(nums[0]!=1) result[1]=1;
else if(nums[n-1]!=n) result[1]=n;
for(int i=0;i<n-1;i++){ if(nums[i]="=" nums[i+1]){ result[0]="nums[i];" } if(nums[i+1]-nums[i]="=" 2){ result[1]="nums[i]+1;" return result; < code></n-1;i++){>
697.数组的度
自己的想法:题目中有三个关键的数字,第一个是每个数字出现次数,第二个是每个数字第一次出现的位置,第三个就是每个数字最后一次出现位置,也可以进一步理解为子串长度。自己的想法是用hashmap来存放,key即为数字,value为数组,数组中第一个值存放出现次数,第二个值存放第一次出现位置,第三次存放最后一次出现位置-第一次出现位置。
public void mytest(){
int[] nums = {1,2};
//计算数组的度 并返回度相同的最小连续子数组的长度
HashMap numsMap = new HashMap();
int max=0;//max记录最大出现次数,min记录最小子串长度
int min=nums.length;
//1是出现次数,2是第一次出现位置,3最后一次出现位置-第一次出现位置(即子串长度
for(int i=0;i<min;i++){ int[] temp="new" int[3]; if(numsmap.containskey(nums[i])){ numsmap.get(nums[i]); temp[0]++; temp[2]="i-temp[1]+1;" numsmap.replace(nums[i],temp); } else{ temp[0]="1;" temp[1]="i;" numsmap.put(nums[i],temp); if(temp[0]>max) max=temp[0];
}
//找出1列最大的,3列最小的
Iterator iterator = numsMap.keySet().iterator();
while (iterator.hasNext()){
Object next = iterator.next();
int[] o = (int[]) numsMap.get(next);
if(o[0] == max){
if(o[2]<min){ min="o[2];" } system.out.println(min); < code></min){></min;i++){>
没想到和官方想法是差不多的。但是这个提交之后运行速度和内存消耗都太大,很不理想。
解题后想法:
参考了解题区一位大佬的想法,只利用一次遍历实现,和上边的想法差不多,但是只在一次数组的遍历中实现,感觉非常巧。
public void thTest(){
int[] nums = {1, 2};
//计算数组的度 并返回度相同的最小连续子数组的长度
Map<integer,int[]> numsMap = new HashMap<>();
int max=0,min=0,len=nums.length;//max记录最大出现次数,min记录最小子串长度
//参考想法:一次遍历实现,遍历一次数组,在遍历中更新max和min。数组存放出现次数,以及第一次出现的位置
for(int i=0;i<len;i++){ int[] temp="numsMap.get(nums[i]);" if(temp="=" null){ int[]{1,i}; numsmap.put(nums[i],temp); } else { temp[0]++; if (temp[0]> max) {
max = temp[0];
min = i - temp[1] + 1;
} else if (temp[0] == max) {
min = Math.min(i - temp[1] + 1, min);
}
}
System.out.println(min);
}
</len;i++){></integer,int[]>
448.找到所有数组中消失的数字
自己的想法:本来是准备对最后返回的list进行一些操作,但是总是超出时间限制,后来突然想到可以对输入的nums数组进行操作。想法是对nums中的数据进行一个重新排列,让数字在对应的位置上,例如4,就在数组的第三个位置上。如果应该在的位置已经有正确的数字了,即重复的时候,就把重复位置设置为0。这样最后的数组就会变成,每个数字都在对应的位置,缺少的数字的位置就是0。然后再对数组进行一个遍历,是0的位置的索引值添加到list中。
public void test(){
int[] nums = {4,3,2,7,8,2,3,1};
List list = new ArrayList();
int temp;
for(int i = 0;i<nums.length;){ int ind="nums[i]-1;" if(nums[i]="=0){" i++; } else if(nums[i]!="i+1){" if(nums[ind]!="nums[i]){" temp="nums[ind];" nums[ind]="nums[i];" nums[i]="temp;" else{ for(int i="0;i<nums.length;i++){" list.add(i+1); system.out.println(list); < code></nums.length;){>
官方想法:官方想法也是对原数组进行操作,不过这个操作更加简单粗暴。每遇到一个数就让这个数正确位置的数值加n,这样这个位置的数必定大于n。再遍历一次数组,如果没有大于n就是缺失的。
public void thTest(){
int[] nums = {4,3,2,7,8,2,3,1};
List list = new ArrayList();
int len = nums.length;
for(int i=0;i<len;i++){ int x="(nums[i]-1)%len;" nums[x]+="len;" } for(int i="0;i<len;i++){" if(nums[i]<="len){" list.add(i+1); system.out.println(list); < code></len;i++){>
442.数组中重复的数据
自己的想法:和448一样,对原数组进行操作。重复的时候加n,这样重复的数字所在的位置就会大于n。
public void mytest(){
int[] nums = {10,2,5,10,9,1,1,4,3,7};
List list = new ArrayList();
int len = nums.length;
int temp;
for(int i=0;i<len;){ int ind="nums[i]-1;" if((i+1)="=nums[i]" || nums[i]>len || nums[ind]>len){
i++;
}
else if(nums[i] != nums[ind]){
temp = nums[i];
nums[i]=nums[ind];
nums[ind]=temp;
}
else if(nums[i] == nums[ind]){
nums[ind]+=len;
i++;
}
}
for(int i=0;i<len;i++){ if(nums[i]>len){
list.add(i+1);
}
}
System.out.println(list);
}
</len;i++){></len;){>
看了大佬的一个解题思路,和448也是一样的,唯一不同的是最后添加到list当中的数值成了大于2*n的。本来也想用448的官方思想解过,但是一直想的是-n,没有仔细观察数组,哎。还是要多观察。
List list = new ArrayList();
int len = nums.length;
for(int num:nums){
int x = (num - 1)%len;
nums[x]+=len;
}
for(int i=0;i<len;i++){ if(nums[i]>2*len){
list.add(i+1);
}
}
</len;i++){>
41.缺失的第一个正数
自己的想法:感觉这几道题都可以用一套代码来做,就是某些细节需要进行修改。想法和448相同,把数字放到该在的位置上。但是遇到0、负数、大于n的数都直接跳过。这样数组就按照顺序摆放了,第一个没有在正确位置上的数就是要求的结果。
public int firstMissingPositive(int[] nums) {
int len = nums.length;
int res=len+1;
int temp;
for(int i = 0;i<nums.length;){ int ind="nums[i]-1;" if(nums[i]<="0" || nums[i]>len){
i++;
}
else if(nums[i]!=i+1){
if(nums[ind]!=nums[i]){
temp=nums[ind];
nums[ind]=nums[i];
nums[i]=temp;
}
else{
nums[i] =0;
i++;
}
}
else i++;
}
for(int i=0;i<len;i++){ if(nums[i]<="0" || nums[i]>len) {
res = i + 1;
break;
}
//System.out.println(nums[i]);
}
return res;
}
</len;i++){></nums.length;){>
官方的解题思路其实是差不多的,但是没有进行交换,而是对数字应该在的位置进行了标记。
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; ++i) {
if (nums[i] <= 0) { nums[i]="n" + 1; } for (int i="0;" < n; ++i) int num="Math.abs(nums[i]);" if (num nums[num - 1]="-Math.abs(nums[num" 1]); (nums[i]> 0) {
return i + 1;
}
}
return n + 1;
}
}
</=>
274.H指数
这个题目没有自己的想法,主要是真的看不懂题目啊!这表达弯弯绕绕的。心情不好,看不下去这题目。
官方想法:用一个标志来表示h,刚开始是0。排序之后从最大的开始加1。这题的难度可能就在看懂题目吧。
public int hIndex(int[] citations) {
int len = citations.length;
int res=0;
Arrays.sort(citations);
for(int i=len-1;i>=0;i--){
if(citations[i]>res) res++;
}
return res;
}
Original: https://www.cnblogs.com/boboray/p/16219509.html
Author: 啵啵ray
Title: 力扣刷题之路-统计数组中的元素
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/685602/
转载文章受原作者版权保护。转载请注明原作者出处!