Как найти повторяющиеся номера и отобразить частоту этого номера - PullRequest
Новая
       4

Как найти повторяющиеся номера и отобразить частоту этого номера

0 голосов
/ 03 ноября 2011

У меня есть 1000 чисел, и я делаю двоичное дерево и сортирую дерево. Он печатает от 0 до 100, а остальные 899 номеров являются дубликатами. Как я могу отслеживать частоту каждого номера. Как например, число 28 появляется 9 раз. Как-то вести счет. Я работал с одним методом, но Idk, если он близок или нет. Я опубликую этот метод в конце. 

   public class bigTree {
 int data; 
 int frequency;
 bigTree Left, Right;


public bigTree makeTree(int x) {
     bigTree p; 
     p = new bigTree();
     p.data = x;
     p.Left = null;
     p.Right = null;

     return p;
 }


 public void setLeft(bigTree t, int x) {

     if (t.Left != null) {
        // setLeft(t.Left, x);
         System.out.println("Error");
     }
     else {


         t.Left = makeTree(x);
     }

 }


 public void setRight(bigTree t, int x) {

     if (t.Right != null) {
         //setRight(t.Right, x);
         System.out.println("Error");
     } else {


         t.Right = makeTree(x);
     } 
 }

 public void insertLocation(bigTree tree, int v) {

    // if (tree.data == v) {

         //findDuplicate(v);
 //}

     if (v < tree.data) {
         if (tree.Left != null){
             insertLocation(tree.Left, v);
         }
         else {
             setLeft(tree, v);
         }
    }
     if (v > tree.data) {
        if (tree.Right != null){
            insertLocation(tree.Right, v);
        } else {
        setRight(tree, v);
        }
     }

    } 


    public void sort(bigTree t) {

     if (t.Left != null) {
         sort(t.Left);

     } 
    System.out.println(t.data + " freq = " + frequency);

     if (t.Right != null) {
         sort(t.Right);
     }

     }

 public void dealArray( String[] x) {
    int convert;

    bigTree tree = makeTree(Integer.parseInt(x[0]));

     for (int i = 1; i < x.length; i++){
         //convert = Integer.parseInt(x[i]);

         insertLocation(tree, Integer.parseInt(x[i]));
        findDuplicate(Integer.parseInt(x[i]));

     }  sort(tree);
 }

---- Метод, который, как я думал, мог бы работать, но не ---- ---- 1004 * 

         public void findDuplicate(int number) {
 bigTree tree, h, q;


 tree = makeTree(number);
    //while (//there are #'s in the list) { //1st while()

        h = tree;
        q = tree;

        while (number != h.data && q != null) { //2nd while()
            h = q; 

            if (number < h.data ) {
                q = q.Left;

            } else { 
                q = q.Right;
            }
        } //end of 2nd while()

        if (number == h.data) {
            //h.frequency++;
            System.out.println("Duplcate: " + number + "freq = " + h.frequency++); 

        } 
        else {
            if (number < h.data) {
                setLeft(h,number);
            }
            else {
                setRight(h, number);
            }

        } 
 //} // End of 1st while() 
        sort(h);

 }

Ответы [ 3 ]

1 голос
/ 03 ноября 2011

PrePost: Если вам нужно использовать поиск в двоичном дереве, похоже, что ваш код выше создает новое дерево для каждого элемента, который он ищет. Вместо этого у вас должно быть одно дерево, которое вы ищете, добавьте / обновите для каждого элемента, который вы ищете.

Предыдущее сообщение: Несмотря на то, что ответ @ Woot4Moo сработает, на подсчет и увеличение добавляются накладные расходы. Я бы предложил использовать класс ListMultimap от Guava для обработки всего этого за вас. ListMultimap 

ListMultimap<Integer, Integer> mymap;
for (Integer value : values){
    mymap.put(value, value);
}

Map<Integer, List<Integer>> asmap = mymap.asMap();
for (Entry<Integer, List<Integer>> entry : asmap.entrySet()){
    System.out.println(String.format("Value %d occurred %d times", entry.getKey(), entry.getValue().size());
}
0 голосов
/ 04 ноября 2011

Думаю, вы движетесь в правильном направлении.

1) Вам нужно отсортировать свои элементы.Есть несколько способов сделать это. введите описание ссылки здесь

2) Вам необходимо найти дубликаты элементов.Это можно сделать, сравнив i-й элемент с элементом i + 1.Вы можете хранить свои ответы на карте.

0 голосов
/ 03 ноября 2011

Итак, первое, что вам нужно сделать, это выбрать структуру данных, которая может представлять значение и количество дубликатов, которые у него есть. Первое, что приходит на ум, это карта

Map<Integer,Integer> // Отслеживает целое число, являющееся ключом, и число, являющееся значением

Итак, что должно произойти, когда вы анализируете свой массив (или любую структуру, из которой вы читаете эти значения), выполните проверку на карте следующим образом:
myMap.contains (integerToCheck);

если содержит возвращает true, вам нужно увеличить значение, сохраненное в myMap для этого ключа. В противном случае вам нужно вставить новый ключ, который использует integerToCheck и новое значение 1.

Затем, чтобы распечатать эти значения, вы должны сделать следующее: 

for(Map.Entry<Integer,Integer> entry: myMap.entrySet())  
{  
    System.out.println(entry.getKey + " : " + entry.getValue());
}
...