首页 > 代码库 > find-all-duplicates-in-an-array(典型的数组中的重复数,不错,我做出来了,可是发现别人有更好的做法)
find-all-duplicates-in-an-array(典型的数组中的重复数,不错,我做出来了,可是发现别人有更好的做法)
https://leetcode.com/problems/find-all-duplicates-in-an-array/
典型的数组中的重复数。这次是通过跳转法,一个个跳转排查的。因为查过的不会重复处理,所以复杂度也是O(n)。
后面发现了别人一个更好的做法。。。如下:
public class Solution { // when find a number i, flip the number at position i-1 to negative. // if the number at position i-1 is already negative, i is the number that occurs twice. public List<Integer> findDuplicates(int[] nums) { List<Integer> res = new ArrayList<>(); for (int i = 0; i < nums.length; ++i) { int index = Math.abs(nums[i])-1; if (nums[index] < 0) res.add(Math.abs(index+1)); nums[index] = -nums[index]; } return res; } }
我的做法:
package com.company; import java.util.ArrayList; import java.util.Iterator; import java.util.List; class Solution { public List<Integer> findDuplicates(int[] nums) { List<Integer> list = new ArrayList<>(); int index = 1; while (index <= nums.length) { int next = nums[index-1]; nums[index-1] = -1; while (next != -1 && next != index && -1 != nums[next-1] && next != nums[next-1]) { int tmp = nums[next-1]; nums[next-1] = next; next = tmp; } if (next == -1) { } if (next == index) { nums[index-1] = next; } else if (-1 == nums[next-1]) { nums[next-1] = next; } else { list.add(next); } index++; } return list; } } public class Main { public static void main(String[] args) { System.out.println("Hello!"); Solution solution = new Solution(); int[] nums = {}; List<Integer> ret = solution.findDuplicates(nums); System.out.printf("ret len is %d\n", ret.size()); Iterator iter = ret.iterator(); while (iter.hasNext()) { System.out.printf("%d,", iter.next()); } System.out.println(); } }
find-all-duplicates-in-an-array(典型的数组中的重复数,不错,我做出来了,可是发现别人有更好的做法)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。