摘要:题目链接一般这种类型的题要,要么给赋值成不在范围内的数,要么到对应位置。
448. Find All Numbers Disappeared in an Array
题目链接:https://leetcode.com/problems...
一般这种类型的题要in place,要么给num[i]赋值成不在范围内的数,要么swap到对应位置。
public class Solution { public ListfindDisappearedNumbers(int[] nums) { List result = new ArrayList(); if(nums.length == 0) return result; // sign as negative when find a number for(int i = 0; i < nums.length; i++) { int index = Math.abs(nums[i]) - 1; nums[index] = -Math.abs(nums[index]); } // find positive number, whose index is not visited for(int i = 0; i < nums.length; i++) { if(nums[i] > 0) result.add(i + 1); } return result; } }
swap的方法见discussion:
https://discuss.leetcode.com/...
public class Solution { public ListfindDisappearedNumbers(int[] nums) { List result = new ArrayList(); if(nums.length == 0) return result; // swap to correct position for(int i = 0; i < nums.length; i++) { while(nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) { swap(nums, i, nums[i] - 1); } } // find positive number, whose index is not visited for(int i = 0; i < nums.length; i++) { if(nums[i] != i + 1) result.add(i + 1); } return result; } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/66657.html
Problem Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements of [1, n] inclusive that do not appear in this array...
Problem Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements of [1, n] inclusive that do not appear in this array...
摘要:如果这个位置的值为正意味着我们还没有对这个元素进行过操作,我们将这个位置的元素的值取负。在整个遍历结束后,没有取负的值的索引,就可以对应到没有在数组出现过的值解法 题目详情 Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others ap...
摘要:题目要求假设一个长度为的整数数组,数组中的元素的值位于区间中。代码如下但是这个实现违背了的空间复杂度这里结果集不视为额外空间。如果当前元素无需进行交换,则指针右移一位。无需进行的场景是指当前元素已经出现在目标位置上了。 题目要求 Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some element...
摘要:题目描述思路先把数组进行升序排序,再进行数组去重,最后循环比较取得结果。升序排序可以使用若要降序排列可以则是数组去重,我使用的中的方法去重,可以参照一行代码实现数组去重数组去重数组去重方法最优解源码排序去重 题目描述 Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appe...
阅读 1563·2021-10-14 09:43
阅读 5291·2021-09-07 10:21
阅读 1244·2019-08-30 15:56
阅读 2086·2019-08-30 15:53
阅读 1201·2019-08-30 15:44
阅读 1967·2019-08-30 15:44
阅读 1277·2019-08-29 17:24
阅读 695·2019-08-29 15:19