Java + Count重复数组来自int数组，而不使用任何Collection或其他中间数组

作为Java面试问题文章的一部分，我有以下问题需要解决。 但我有点想知道如何在没有任何Collection或中间数组的情况下实现它。

问题： – 从int数组中计算重复项，而不使用任何Collection或其他中间数组

Input values:- {7,2,6,1,4,7,4,5,4,7,7,3, 1} Output:- Number of duplicates values: 3 Duplicates values: 7, 4, 1 

我已经实施了以下解决方案，但没有完成一个。 任何人都有一些想法？ 谢谢。

 public static void duplicate(int numbers[]) { for (int i = 0; i < numbers.length; i++) { boolean duplicate = false; int j = 0; while (j < i){ if ((i != j) && numbers[i] == numbers[j]) { duplicate = true; } j++; } if (duplicate) { System.out.print(numbers[i] + " "); } } } 

Answer 1

解决此问题的最简单方法是首先对数组进行排序，然后在遇到它们时遍历计算重复数组的数组：

 int[] numbers = new int[]{7,2,6,1,4,7,4,5,4,7,7,3,1}; int temp = 0; // I chose to do a bubble sort of the array, // but you are free to use any method you wish (eg Arrays.sort) System.out.print("Duplicates values: "); for (int i=0; i < numbers.length; ++i) { for (int j=1; j < (numbers.length - i); ++j) { if (numbers[j-1] > numbers[j]) { temp = numbers[j-1]; numbers[j-1] = numbers[j]; numbers[j] = temp; } } } // walk through the sorted array and count duplicates int numDup = 0, dupCount = 0; int previous = -1; for (int i=0; i < numbers.length; ++i) { if (numbers[i] == previous) { ++numDup; if (numDup == 1) { ++dupCount; if (dupCount == 1) { System.out.print(numbers[i]); } else { System.out.print(", " + numbers[i]); } } } else { previous = numbers[i]; numDup = 0; } } System.out.println("\nNumber of duplicates values: " + dupCount); 

输出：

 Duplicates values: 1, 4, 7 Number of duplicates values: 3 

请注意，我的输出顺序与您的输出顺序相反，因为您需要先了解整个数组，然后才能知道有多少重复项。 此外，我将指出此解决方案使用的唯一状态是输入数组本身，以及此处和那里的几个int varibles。

此代码已在IntelliJ中测试过，它可以正常工作。

Answer 2

同意Tim @ tim-biegeleisen。 只是微小的改变。 使用数组对数组进行排序。

公共类DuplicateClass {

 public static void main(String[] args) { int[] values = { 7, 2, 6, 1, 4, 7, 4, 5, 4, 7, 7, 3, 1 }; duplicate(values); } public static void duplicate(int numbers[]) { Arrays.sort(numbers); int previous = numbers[0] - 1; ; int dupCount = 0; for (int i = 0; i < numbers.length; ++i) { if (numbers[i] == previous) { ++dupCount; } else { previous = numbers[i]; } } System.out.println("There were " + dupCount + " duplicates in the array."); } 

}

Answer 3

这些都是很好的答案。 另一个是使用int / double并在遇到数字时设置它的位。 如果数组的值小于32/64，则此方法有效，具体取决于您使用的类型。

下面是如何使用整数执行此操作的示例。

 public class SetThoseBits{ // 0000 0000 0000 0000 000 0000 0000 0000 public static int data = 0; public static void main(String [] args){ // Gurantee that the numbers are less than 32 int[] values = { 7, 2, 6, 1, 4, 7, 4, 5, 4, 7, 7, 3, 1 }; duplicates(values); } public static void duplicates(int [] values){ for(int i : values){ if(testBit(i)){ System.out.println("Duplicate :" + i); } else{ setBit(i); } //printBits(); } System.out.println("Finished!"); } // Sets the bit at a specific position public static void setBit(int index){ data = data | (1 << index); } // This function will test the bit at the index of the given integer // If it's set, it returns true public static boolean testBit(int index){ return ((data & (1 << index)) != 0); } public static void printBits(){ for (int x = 31; x >= 0; x--){ if(testBit(x)){ System.out.print("1"); } else{ System.out.print("0"); } } System.out.println("0"); } } 

我相信其他答案在给出你的问题时会更好。但是，作为一种替代方案，这表明你正在动态地思考它。 如果问题的要求稍有改变，这个答案可能更合适。

此外，如果您只需要尽可能小地跟踪重复项，您可以执行类似于上面的操作或使用java的BitSet类来使您的生活更轻松。

http://docs.oracle.com/javase/7/docs/api/java/util/BitSet.html

编辑：如果您创建一个包含像BitSet类一样的字节数组的函数，也可以使值高于64。 对于这个确切的问题，考虑到不使用数组或集合的约束，这没有用。

Answer 4

保留一个额外的变量来维持计数，再加上初始阶段的数组排序。

 public static void main(String[] args) { int[] numbers = { 7, 2, 6, 1, 4, 7, 4, 5, 4, 7, 7, 3, 1 }; Arrays.sort(numbers); System.out.println("Sorted Array is :: = " + Arrays.toString(numbers)); int count = 0; int tempCount = 0; // to keep local count of matched numbers String duplicates = ""; for (int i = 1; i < numbers.length; i++) { if (numbers[i] == numbers[i - 1]) { if ((tempCount == 0)) { // If same number is repeated more than // two times, like 444, 7777 count = count + 1; tempCount = tempCount + 1; duplicates = duplicates.concat(Integer.toString(numbers[i]) + ","); } } else { tempCount = 0; } } System.out.println("No of duplicates :: = " + count); System.out.println("Duplicate Numbers are :: = " + duplicates); } 

产量

 Sorted Array is :: = [1, 1, 2, 3, 4, 4, 4, 5, 6, 7, 7, 7, 7] No of duplicates :: = 3 Duplicate Numbers are :: = 1,4,7, 

Answer 5

  int numbers[]={7,2,6,1,4,7,4,5,4,7,7,3, 1}; String temp=""; int count=0; Arrays.sort(numbers); for (int i = 0; i < numbers.length; i++) { boolean duplicate = false; for(int j = 0; j < numbers.length; j++) { if ((i != j) && numbers[i] == numbers[j]) { duplicate = true; } } if (duplicate) { if(!temp.contains(""+numbers[i])) { temp+=numbers[i]+", ";//adding a number if its duplicate count++;//counting unique duplicate number } System.out.print(numbers[i] + " "); } } System.out.println("\nDuplicates are: "+temp+" count: "+count); 

输出：

  Duplicates are: 1, 4, 7, count: 3 

Answer 6

我想，这也是一种计算它的方法：

 public class App { public static void main(String[] args) { Integer[] intArr = { 7, 2, 6, 1, 4, 7, 4 }; List listInt = Arrays.asList(intArr); Map map = new HashMap<>(); Integer dupCount = 0; StringBuilder dupvalues = new StringBuilder(); for (Integer integer : intArr) { int times = Collections.frequency(listInt, integer); if (map.containsKey(integer)) { dupvalues.append(integer).append(","); dupCount++; } else map.put(integer, times); } System.out.println("There were " + dupCount + " duplicates in the array. The value are : "+dupvalues); } } 

Answer 7

这是我能想到的最简单的解决方案。 我刚添加了一个额外的计数器，以便忽略数组中仍有两次或更多次重复的整数。

 static int findNumber(int[] arr) { int duplicateCounter = 0; System.out.print("Duplicates: "); for(int i = 0; i < arr.length; i++) { boolean duplicate = false; int numOfOccurrences = 1; for (int j = (i+1); j < arr.length; j++) { if (arr[i] == arr[j]) { numOfOccurrences++; duplicate = true; } } if(numOfOccurrences == 2 && duplicate == true) { duplicateCounter++; System.out.print(arr[i] + " "); } } return duplicateCounter; } 

我的测试运行： 测试运行

输入：1,2,3,4,2,4,1,1,1

重复：2 4 1

重复次数：3

Answer 8

有一种方法可以使用Math.abs。 你应该检查标志是否正面。如果它是正面的，那么让它为负面。 如果是负数，那么这是重复的数字或重复的数字。 示例：A [] = {1,1,2,3,2} i = 0; 检查A [abs（A [0]）]的符号，即A [1]。 A [1]是正数，因此将其设为负数。 数组现在变为{1，-1,2,3,2}

I = 1; 检查A [abs（A [1]）]的符号，即A [1]。 A [1]是负数，因此A [1]是重复。 然后将所有重复的数字放入列表中并打印列表的大小。

python中的代码是

  from astropy.extern.ply.cpp import xrange def printrepeat(arr): print("The repeating elements are: ") list =[] for i in xrange(0,len(arr)): ch = abs(arr[i]) if arr[ch] > 0: arr[ch] = (-1)*arr[ch]; else: list.append(arr[ch]) print(len(list)) # driver code arr = [1 , 3 , 2 , 2 , 1,3] printrepeat(arr) 

解决方案2：2指针

 class Abc1{ public static void main(String[] args) { int[] a = {1, 1, 2, 3, 2}; countDuplicates(a); } private static void countDuplicates(int[] a) { int c = 0 ; for(int i = 0 ; i < a.length ; i++) { for(int j = i+1 ; j < a.length;j++) { if(a[i] == a[j]) {c++ ;} }//for }//for1 System.out.println("dup => " + c); } } 

解决方案3：HashSet

 class Abc1{ public static void main(String[] args) { String a = "Gini Gina Protijayi"; countDuplicates(a); } private static void countDuplicates(String aa) { List list= new ArrayList<>(); Set set = new HashSet<>(); // remove all the whitespaces String a = aa.replaceAll("\\s+",""); for( char ch : a.toCharArray()) { if(!set.contains(ch)) { set.add(ch); }//if else {if(!list.contains(ch) ) {list.add(ch);} } }//for System.out.println("number of duplicate characters in the string =>" + list.size()); System.out.println(list); } } 

解决方案：4（与解决方案1相同的概念，但代码是Java）

 import java.util.ArrayList; import java.util.List; public class AA { public static void main(String[] args) { int a[] = {4, 2, 4, 5, 2, 3, 1}; printRepeat(a); } private static void printRepeat(int[] a) { List list = new ArrayList<>(); for (int i = 0; i < a.length; i++) { if( a[Math.abs(a[i])] > 0) { a[Math.abs(a[i])] = (-1)* a[Math.abs(a[i])] ; }//if else { System.out.println( "Duplicate numbers => " + Math.abs(a[i]) ); list.add(Math.abs(a[i])); System.out.println("list => " + list); System.out.println("list.size() or the count of duplicates => " + list.size()); }//else }//for }//print }