【算法】【Java】寻找数组中任一一个重复的数字
2022/1/31 17:40:35
本文主要是介绍【算法】【Java】寻找数组中任一一个重复的数字,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
剑指Offer:第三题
在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的,找出数组中所有重复的数字。
解法一:
先排序在寻找
采用快速排序,时间复杂度是O(nlog(n))
package algorithm.test3; import java.util.Arrays; import java.util.HashSet; public class Q1 { public static void main(String[] args) { int[] test = new int[]{2, 3, 1, 0, 2, 5, 3}; quickSort(0,test.length - 1,test); HashSet<Integer> integers = new HashSet<>(); System.out.println(Arrays.toString(test)); for (int i = 0; i < test.length; i++) { if (i == 0) { continue; } if (test[i-1] == test[i]) { integers.add( test[i]); } } System.out.println(integers); } public static void quickSort(int start,int end,int[] test) { if (start < end) { int partion = getIndex(start, end, test); quickSort(start, partion, test); quickSort(partion + 1, end, test); } } private static int getIndex(int start, int end, int[] test) { // 基准数据 int tmp = test[start]; while (start < end) { // 当队尾的元素大于等于基准数据时,向前挪动high指针 while (start < end && test[end] >= tmp) { end--; } // 如果队尾元素小于tmp了,需要将其赋值给low test[start] = test[end]; // 当队首元素小于等于tmp时,向前挪动low指针 while (start < end && test[start] <= tmp) { start++; } // 当队首元素大于tmp时,需要将其赋值给high test[end] = test[start]; } // 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置 // 由原理部分可以很清楚的知道low位置的值并不是tmp,所以需要将tmp赋值给arr[low] test[start] = tmp; return start; // 返回tmp的正确位置 } }
解法二:
原地算法:
时间复杂度O(n)
空间复杂度O(1)
public class Method3 { public static void main(String[] args) { int[] test = new int[]{2, 3, 1, 0, 2, 5, 3}; System.out.println(answer2(test)); } public static HashSet<Integer> answer2(int[] test) { HashSet<Integer> integers = new HashSet<>(); for (int i = 0; i < test.length; i++) { if (test[i] != i) { while (test[i] != i) { if(test[i] == test[test[i]]){ integers.add(test[i]); break; } int temp = test[i]; test[i] = test[test[i]]; test[temp] = temp; } } } return integers; } }
这篇关于【算法】【Java】寻找数组中任一一个重复的数字的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)