数组中重复的数字
import java.util.Map;
import java.util.HashMap;
public class Solution {
public boolean duplicate(int numbers[],int length,int [] duplication) {
if(numbers == null || numbers.length ==0){
return false;
}
for(int i =0;i<numbers.length;i++){
while (numbers[i] != i) {
if(numbers[i] == numbers[numbers[i]]){
duplication[0] = numbers[i];
return true;
}else{
swap(numbers,i,numbers[i]);
}
}
}
duplication[0] = -1;
return false;
}
public void swap(int numbers[],int start,int end){
int temp =0;
temp = numbers[start];
numbers[start] = numbers[end];
numbers[end] = temp;
}
}题目
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
思路
还可以把当前序列当成是一个下标和下标对应值是相同的数组（时间复杂度为O(n),空间复杂度为O(1)）； 遍历数组，判断当前位的值和下标是否相等：
- 若相等，则遍历下一位；
- 若不等，则将当前位置i上的元素和a[i]位置上的元素比较：若它们相等，则找到了第一个相同的元素；若不等，则将它们两交换。换完之后a[i]位置上的值和它的下标是对应的，但i位置上的元素和下标并不一定对应；重复2的操作，直到当前位置i的值也为i，将i向后移一位，再重复2。
本文采用思路3，如果还是不懂，看下面的实例分析就懂了！
举例说明：{2,3,1,0,2,5,3}
- 0(索引值)和2(索引值位置的元素)不相等，并且2(索引值位置的元素)和1(以该索引值位置的元素2为索引值的位置的元素)不相等，则交换位置，数组变为：{1,3,2,0,2,5,3}；
- 0(索引值)和1(索引值位置的元素)仍然不相等，并且1(索引值位置的元素)和3(以该索引值位置的元素1为索引值的位置的元素)不相等，则交换位置，数组变为：{3,1,2,0,2,5,3}；
- 0(索引值)和3(索引值位置的元素)仍然不相等，并且3(索引值位置的元素)和0(以该索引值位置的元素3为索引值的位置的元素)不相等，则交换位置，数组变为：{0,1,2,3,2,5,3}；
- 0(索引值)和0(索引值位置的元素)相等，遍历下一个元素；
- 1(索引值)和1(索引值位置的元素)相等，遍历下一个元素；
- 2(索引值)和2(索引值位置的元素)相等，遍历下一个元素；
- 3(索引值)和3(索引值位置的元素)相等，遍历下一个元素；
- 4(索引值)和2(索引值位置的元素)不相等，但是2(索引值位置的元素)和2(以该索引值位置的元素2为索引值的位置的元素)相等，则找到了第一个重复的元素。
牛客网通过的代码
import java.util.Map;
import java.util.HashMap;
public class Solution {
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
// Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
// 这里要特别注意~返回任意重复的一个，赋值duplication[0]
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
public boolean duplicate(int numbers[],int length,int [] duplication) {
if(numbers == null || length ==0){
return false;
}
Map<Integer,Integer> maps = new HashMap<Integer,Integer>();
for(int i =0;i<length;i++){
if(maps.get(numbers[i]) == null){
maps.put(numbers[i],1);
}else{
maps.put(numbers[i],2);
}
}
for(int i =0;i<length;i++){
if(maps.get(numbers[i]) ==2){
duplication[0] = numbers[i];
return true;
}
}
return false;
}
}最快的方法
public class duplicate {
public static void main(String[] args) {
int[] numbers1 = {2, 3, 1, 0, 2,5,3};
System.out.println(duplicate(numbers1));
}
public static int duplicate(int[] number) {
if (number == null || number.length < 1) {
return -1;
}
// 判断输入的是否在[0, number.length-1]之间
for (int i : number) {
if (i < 0 || i >= number.length) {
return -1;
}
}
for (int i = 0; i < number.length; i++) {
// 当number[i]与i不相同的时候一直交换
while (number[i] != i) {
if (number[i] == number[number[i]]) {
return number[i];
}
// 如果不同就交换
else {
swap(number, i, number[i]);
}
}
}
return -1;
}
private static void swap(int[] number, int x, int y) {
int tmp = number[x];
number[x] = number[y];
number[y] = tmp;
}
}
使用额外空间1
//使用额外空间的方法。
public boolean duplicate2(int numbers[],int length,int [] duplication) {
if(numbers == null || numbers.length ==0) {
duplication[0] = -1;
return false;
}
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < length; i++) {
if(list.contains(numbers[i])) {
duplication[0] = numbers[i];
return true;
}
list.add(numbers[i]);
}
return false;
}
使用额外空间2
//使用额外空间的方法。
public boolean duplicate4(int numbers[],int length,int [] duplication) {
if(length < 2||numbers==null){
return false;
}
Set<Integer> ss = new HashSet<Integer>();
for (int i = 0; i < numbers.length; i++) {
if (ss.contains(numbers[i])) {
duplication[0] = numbers[i];
return true;
} else {
ss.add(numbers[i]);
}
}
return false;
}
LeetCode
给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。
找到所有出现两次的元素。
你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？
示例：
输入:
[4,3,2,7,8,2,3,1]
输出:
[2,3]
方法1超时
public List<Integer> findDuplicates(int[] numbers) {
List<Integer> duplication = new ArrayList<>();
if(numbers == null || numbers.length ==0) {
return duplication;
}
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < numbers.length; i++) {
if(list.contains(numbers[i])) {
duplication.add(numbers[i]);
}
list.add(numbers[i]);
}
return duplication;
}
方法2 set
public List<Integer> findDuplicates(int[] numbers) {
List<Integer> duplication = new ArrayList<>();
if(numbers == null || numbers.length ==0) {
return duplication;
}
Set<Integer> ss = new HashSet<>();
for (int i = 0; i < numbers.length; i++) {
if (ss.contains(numbers[i])) {
duplication.add(numbers[i]);
} else {
ss.add(numbers[i]);
}
}
return duplication;
}
方法3 hashset
class Solution {
public List<Integer> findDuplicates(int[] nums) {
HashSet<Integer> list = new HashSet<Integer>();
List<Integer> resultList = new ArrayList<Integer>();
for (int i : nums) {
if (!list.add(i)) {
resultList.add(i);
}
}
return resultList;
}
}
京公网安备 11010502036488号