Java + Count 从 int 数组中重复，而不使用任何集合或其他中间数组

Java + Count duplicates from int array without using any Collection or another intermediate Array

提问by Channa

As a part of the Java interview question paper I have got following issue to solve. But I am bit wonder whether how can I implement it without any Collection or intermediate Array.

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

Question:- Count duplicates from int array without using any Collection or another intermediate Array

问题：- 在不使用任何集合或其他中间数组的情况下从 int 数组中计算重复项

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

I have implemented following solution but was not completed one. Any one has some idea? Thanks.

我已经实施了以下解决方案，但尚未完成。有人有什么想法吗？谢谢。

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] + " ");
        }
    }
}

采纳答案by Tim Biegeleisen

The easiest way to solve this problem is to sort the array first, and then just walk through the array counting duplicates as you encounter them:

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

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 (e.g. 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);

Output:

输出：

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

Note that my output order is reverse of what you have, because you need to read through the entire array before you know how many total duplicates you have. Also, I will point out that the only state this solution uses is the input array itself, plus a couple of intvaribles here and there.

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

This code has been tested in IntelliJ and it works correctly.

此代码已在 IntelliJ 中进行了测试，并且可以正常工作。

回答by SatyaTNV

    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);

Output:

输出：

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

回答by Mukesh Kumar

Agreed to Tim @tim-biegeleisen. Just minor change. Use the Arrays to sort the array.

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

public class 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.");
    }
}

回答by Ankur Singhal

Keeping one extra variable for maintaining count, plus sorting of array in the initial phase.

保留一个额外的变量用于维护计数，并在初始阶段对数组进行排序。

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);
    }

output

输出

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,

回答by Pumphouse

These are all great answers. One other is to use an int/double and set it's bits when you encounter a number. This works if the array's values are less than 32/64 depending on the type you use.

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

Below is an example of how you would do that with an integer.

下面是一个示例，说明如何使用整数执行此操作。

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");
    }

}

I believe the the other answers are better given your question..but demonstrating this as an alternative shows that you're thinking about it dynamically. If the requirements of the question changed a little this answer might be more appropriate.

我相信鉴于您的问题，其他答案会更好……但是将其作为替代方案进行展示表明您正在动态地考虑它。如果问题的要求稍有变化，则此答案可能更合适。

Further if you only need to keep track of duplicates given the smallest footprint possible, you could do something similar to what is above or use java's BitSet class to make your life easier.

此外，如果您只需要在尽可能小的占用空间的情况下跟踪重复项，您可以执行与上述类似的操作或使用 java 的 BitSet 类让您的生活更轻松。

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

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

Edit:It is also possible to have values higher than 64 given that you create a function that holds an array of bytes like the BitSet class. For this exact question this isn't helpful given the constraint to not use an array or collection.

编辑：如果您创建了一个包含字节数组（如 BitSet 类）的函数，则值也可能高于 64。对于这个确切的问题，鉴于不使用数组或集合的约束，这没有帮助。

回答by Pumphouse

I think, this is also a way to calculate it:

我想，这也是一种计算方式：

public class App {
    public static void main(String[] args) {
        Integer[] intArr = { 7, 2, 6, 1, 4, 7, 4 };
        List<Integer> listInt = Arrays.asList(intArr);

        Map<Integer, Integer> 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);
    }
}

回答by jaymaytay

This is the simplest solution I can think of. I just added an extra counter so that integers with two or more repetitions still in the array are ignored.

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

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;
}

My test run: Test run

我的试运行：试运行

Input: 1, 2, 3, 4, 2, 4, 1, 1, 1

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

Duplicates: 2 4 1

重复：2 4 1

Number of duplicates: 3

重复次数：3

回答by Soudipta Dutta

There is one method where you can use Math.abs. You should check for the sign positive.If it is positive then make it negative. If negative then that's the duplicated number or the repeated number. Example: A[] = {1, 1, 2, 3, 2} i=0; Check sign of A[abs(A[0])] which is A[1]. A[1] is positive, so make it negative. Array now becomes {1, -1, 2, 3, 2}

有一种方法可以使用 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; Check sign of A[abs(A[1])] which is A[1]. A[1] is negative, so A[1] is a repetition. Then just put all those repeated numbers into a list and print the size of the list.

我=1; 检查 A[abs(A[1])] 的符号，即 A[1]。A[1] 是负数，所以 A[1] 是一个重复。然后只需将所有这些重复的数字放入一个列表中并打印列表的大小。

The code in python is

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)            

Solution 2: Taking 2 pointers

解决方案 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);
    }

}

Solution 3: HashSet

解决方案 3：HashSet

class Abc1{
    public static void main(String[] args) {

  String a = "Gini Gina Protijayi";
   countDuplicates(a);
}

    private static void countDuplicates(String aa) {
        List<Character> list= new ArrayList<>();
       Set<Character> 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);
    }

}

Solution:4(same concept as solution 1 but code is in Java)

解决方案：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<Integer> 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
    }

回答by Lampard

Below method not use any collection, just use Arrays.sort() method to help sort array into ascending order as default, e.g array = [9,3,9,3,9] will sort into [3,3,9,9,9].If input [9,9,9,9,9], expected result is 1, since only repeated number is 9.If input [9,3,9,3,9,255,255,1], expected result is 3, since repeated numbers are 3,9,255. If input [7,2,6,1,4,7,4,5,4,7,7,3,1], expected result is 3, since repeated numbers are 1,4,7.

下面的方法不使用任何集合，只使用 Arrays.sort() 方法默认帮助将数组按升序排序，例如 array = [9,3,9,3,9] 将排序为 [3,3,9,9 ,9]。如果输入[9,9,9,9,9]，预期结果为1，因为只有重复次数为9。如果输入[9,3,9,3,9,255,255,1]，预期结果为3 ，因为重复的数字是 3,9,255。如果输入 [7,2,6,1,4,7,4,5,4,7,7,3,1]，预期结果是 3，因为重复的数字是 1,4,7。

public static int findDuplicateCountsInArray(int[] nums) {
    // Sort the input array into default ascending order
    Arrays.sort(nums);
    int prev = nums[0];
    int count = 0;
    // Recording a number already a repeated one
    // e.g [9,9,9] the 3rd 9 will not increase duplicate count again
    boolean numAlreadyRepeated = false;
    for(int i = 1; i < nums.length; i++) {
        if(prev == nums[i] && !numAlreadyRepeated) {
            count++;
            numAlreadyRepeated = true;
        } else if(prev != nums[i]) {
            prev = nums[i];
            numAlreadyRepeated = false;
        }
    }
    return count;
}

回答by Mayank Shekhar

Here I have written code in JAVA. also the inputted numbers, have been considered as String. This question has also been added to CODEWARS. and I hope this simple solution helps You

这里我用JAVA写了代码。输入的数字也被视为字符串。此问题也已添加到 CODEWARS 中。我希望这个简单的解决方案可以帮助您

public class countingduplicates {
  public static void main(String[] args) {
    int i=0,j=0,c=0,a=0;
    String text="7261474547731";
    text=text.toLowerCase();

    for(i=0; i<text.length(); i++) {
      for(j=0; j<text.length(); j++) {
        if(text.charAt(i) == text.charAt(j)) { 
          c++;
        }
      }

      System.out.println(text.charAt(i) + " occured " + c + " times");
      if(c>1) {
        a++;
      }  

      String d = String.valueOf(text.charAt(i)).trim();
      text = text.replaceAll(d,"");
      c = 0;
      i = 0; //cause i have trimmed the string and by default i increases by 1, so i have to assign it =0
      j = 0; //cause i have trimmed the string and by default j increases by 1, so i have to assign it =0
    }
  System.out.println("Total count of Duplicates:" + a);
  }
}