在整数组中找到第一个重复元素。2 P: k2 q) S1 J; ]$ Z6 k. v
例如： " x: ]7 `/ c7 A3 [/ RInput: array[] = Output: 7 [7 is the first element actually repeats] % z5 X2 [2 U8 }解决方案: * N0 P- |5 ]9 u: x) q1 C, a5 S- Z+ `
一个简单的解决方案是使用两个循环。外循环将循环，内循环将检查元素是否重复，但该解决方案的时间复杂度为 o(n^2)。( S$ X/ ^( ^6 q$ o7 a7 I
另一个解决方案是创建另一个数组并对其进行排序。从原始数组中选择元素，并使用二进制搜索在排序数组中搜索元素，但解决方案的时间复杂性是 o(n^logn)。! J+ s6 @2 ?9 Y% n
我们能做得更好吗？ ! F0 x2 w( J4 a8 {$ }& z是的，我们可以从右到左迭代并使用HashSet来跟踪 minimumIndex ; d# z. @; C0 E$ i$ a r用 -1 初始化 minimumIndex* 从右到左迭代输入数组* 如果元素存在于 Hashset 中，则更新 minimumIndex *否则，将元素添加到集合中 ! }8 Z( M' C* q; M9 W8 O) y9 ^一旦我们完成迭代，我们最终会得到 minimumIndex1 S8 @ A) u. r. J8 a3 g
在整数组中找到第一个重复元素的程序& ~8 D. x9 V- d
MaximumOccurringCharacterMain.java0 c0 t/ R1 ?; m9 z6 v. P R
package org.arpit.java2blog;/* Java program to find first repeating element in arr[] */import java.util.*; public class FirstRepatingElementMain This function prints the first repeating element in arr static int getFirstRepeatingElementArray(int array[]) Initialize index of first repeating element int minimumIndex = -1. Creates an empty hashset HashSet[I] set = new HashSet()； Iterate over the input array from right to left for (int i=array.length-1; i>=0; i--) If set contains the element,update minimum index if (set.contains(array<i>)) minimumIndex = i; else // Else add element to hash set set.add(array<i>); return minimumIndex; public static void main (String[] args) throws java.lang.Exception int array[] = int min=getFirstRepeatingElementArray(array); // Print the result if (min != -1) System.out.println("The first repeating element in array is " array[min]); else System.out.println("There are no repeating elements"); } 当您操作上述程序时，您将获得以下输出： - U* |' a8 _# x) \8 G0 tThe first repeating element in array is
技术问答
204 人阅读
|
0 人回复
|
2023-09-12
