算法系列之原地算法(in 基金转换算法是什么意思啊

一、原地算法简介

    在计算机科学中，一个原地算法（in-place algorithm）基本上不需要额外辅助的数据结构,然而,允许少量额外的辅助变量来转换数据的算法。当算法运行时，输入的数据通常会被要输出的部分覆盖掉。不是原地算法有时候称为非原地（not-in-place）或不得其所（out-of-place）。–摘自维基百科。     在计算复杂性理论中，原地算法包含使用O(1)空间复杂度的所有算法，DSPACE(1)类型。

二、例子 题目描述

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。 示例 1:

给定数组 nums = [1,1,2],函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。你不需要考虑数组中超出新长度后面的元素。

示例2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。你不需要考虑数组中超出新长度后面的元素。

参考代码1:

public int removeDuplicates(int[] nums) { int i = 0; for (int n : nums) if (i == 0 || n > nums[i - 1]) nums[i++] = n; return i; }

思路解析：(以示例2为例)

i=0：仅限第一个元素。 因为升序排序，当nums[i]开始重复时，i++进行；直到n>nums[i-1]出现时，把nums[i++] = n进行赋值。当nums[i++] = n执行完了，去重的工作也就结束了。

参考代码2:

public int removeDuplicates(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int pos = 0, count = 1; for (int i = 0; i < nums.length; i++) { if (nums[pos] == nums[i]) { nums[pos] = nums[i]; } else { pos++; nums[pos] = nums[i]; count++; } } return count; }

代码1是代码2的简化版。