定制高端网站建设设计,成全视频免费观看在线看厨房电视剧下载,页面优化算法,杭州建设网杭州造价平台题解一#xff1a; 正负模拟哈希#xff1a;偏技巧类的题目#xff0c;在无法使用额外空间的情况下#xff0c;只能在原数组中做出类似哈希表的模拟。除去数值#xff0c;我们还可以用正负来表示下标值的出现情况。首先#xff0c;数组中存在正负数和0#xff0c;而负数…
题解一 正负模拟哈希偏技巧类的题目在无法使用额外空间的情况下只能在原数组中做出类似哈希表的模拟。除去数值我们还可以用正负来表示下标值的出现情况。首先数组中存在正负数和0而负数和0对结果是没有影响的我们将它们设置为一个较大的正数0x3f3f3f3f如此当前数组中就只存在正整数。
设想一下没有出现的最小的正整数可能的值一定是在[1,nums.length1]中的原因是数组最多只能有nums.length个正整数。因此下一步我们将处于这个范围内出现过的值nums[值-1]设置为负数来表示这个值已经出现过了。这里需要注意三点第一[1,nums.length1]中只有[1,nums.length]可以用下标表示而存储结果的值result可以初始化为nums.length1。第二我们需要用绝对值来表示这些正整数因为先出现的值可能会将后出现的值设置为负数。第三使用乘-1的方式出现偶数次的数值仍然会被判断为未出现过因此必须加上判断语句。
最后我们遍历数组找到的第一个正数对应的下标1就是未出现过的最小正整数。
class Solution {public int firstMissingPositive(int[] nums) {int n nums.length;int result nums.length 1;for (int i 0; i n; i) {if (nums[i] 0) nums[i] 0x3f3f3f3f;}for (int i 0; i n; i) {int temp Math.abs(nums[i]);if (temp n nums[temp - 1] 0) nums[temp - 1] * -1;}for (int i 0; i n; i) {if (nums[i] 0) {result i 1;break;}}return result;}
}
