义乌做网站的电话,wordpress用的编辑器外接,个人客户管理app免费,电商专员是做什么的写在前面 最近想复习一下数据结构与算法相关的内容#xff0c;找一些题来做一做。如有更好思路#xff0c;欢迎指正。 目录 写在前面一、场景描述二、具体步骤1.环境说明2.代码 写在后面 一、场景描述 在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内#xff0c;判…写在前面 最近想复习一下数据结构与算法相关的内容找一些题来做一做。如有更好思路欢迎指正。 目录 写在前面一、场景描述二、具体步骤1.环境说明2.代码 写在后面 一、场景描述 在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内判断该数组中是否有重复的数。 示例 [2,3,1,0,2,5,3] 返回 true 可以使用Map作为过滤思路也很简单。循环数组中的元素不存在就加入map存在就返回 true循环结束没找到直接返回 false。可参考【数组】-找出数组中第一个重复的数字 也有一种类似排序的方式可以实现时间复杂度O(n)空间复杂度O(1)。由于题目的条件约束是数组中的元素值都在 0 - n-1之间那么我们就可以给数组中每个元素都放到对应数组的索引位置上比如当前元素的值为2我们就把2放到 array[2] 的位置上如果在索引位置上比如array[2]找到了同样的元素就说明有重复值否则交换继续循环。直至循环结束说明没有找到重复值具体参见代码中的思路。不过这种方式也仅限于算法。日常编码我们大概率用不到这种方式因为多数情况下我们不会去改变原数组的数据或者位置。 二、具体步骤
1.环境说明
名称说明IntelliJ IDEA2019.2
2.代码
以下为Java版本实现 public class ArrayIsDuplicateTest {public static void main(String[] args) {
// int[] array {2, 3, 1, 0, 2, 5, 3};int[] array {0, 1};System.out.println(isDuplicate(array));}/*** 思路** 条件约束* 1.n个元素* 2.数组中所有数组都是 0 - n-1 之间** 这2个条件意味着* 如果数组不重复0 - n-1的数字必定都在数组中* 重复0 - n-1的数字至少有一个在数组中重复** 循环数组* while 判断 当前元素和索引下表值是否相同* 不相同判断当前元素的值 array[i] 是否和当前元素值作为索引在数组位置上的值 array[array[i]] 是否相等* 相等直接返回 true* 否则就把 array[i] 和 array[array[i]] 的值交换相当于给 array[i] 找到了正确的位置继续while循环* 说明while循环的结束条件要么是找到相同的元素了直接返回要么是交换后当前元素的位置也正确了跳出while循环继续数组for的下一轮循环** 数组循环结束每个元素都找到了正确的位置即没有找到重复的数返回false** param array* return*/private static boolean isDuplicate(int[] array) {for (int i 0; i array.length; i) {while (array[i] ! i) {if (array[i] array[array[i]]) {return true;}// 交换int temp array[array[i]];array[array[i]] array[i];array[i] temp;}}return false;}
} 写在后面 如果本文内容对您有价值或者有启发的话欢迎点赞、关注、评论和转发。您的反馈和陪伴将促进我们共同进步和成长。
