Максимальное количество повторяющихся строк в массиве

Question

Проблема

как получить максимальное количество повторяющихся строк в массиве, используя только операции над массивами в Java?

так что я попал в этот вопрос в тесте и не мог понять это. предположим, у нас есть массив строк.

str1[] = { "abbey", "bob", "caley", "caley", "zeeman", "abbey", "bob", "abbey" }
str2[] = { "abbey", "bob", "caley", "caley", "zeeman", "abbey", "bob", "abbey", "caley" }

1. в str1 аббатстве было максимально повторено, поэтому аббатство должно быть возвращено и

2. в str2 аббатстве и Кейли имеют одинаковое количество повторений, поэтому мы берем максимальный алфавит в качестве победителя и возвращаемся ( Кейли здесь).

   c> a

так что я пытался до

import java.util.*;
public class test {
    static String highestRepeated(String[] str) {
        int n = str.length, num = 0;
        String temp;
        String str2[] = new String[n / 2];

        for (int k = 0;k < n; k++) {  // outer comparision
            for (int l = k + 1; l < n; l++) { // inner comparision
                if (str[k].equals(str[l])) {
                    // if matched, increase count
                    num++;
                }
            }
             // I'm stuck here
        }

        return result;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("enter how many votes");
        int n = sc.nextInt();
        String[] str = new String[n];
        for (int i = 0; i < n; i++) {
            Str[i] = sc.nextLine();

        }
        String res = highestRepeated(str);
        System.out.println(res + " is the winner");
    }
}

Итак, как мне считать количество вхождений каждой строки с и присоединить ее к самой строке.

Все это, без использования карты и хэширования, а только с использованием массивов?

Answer 1

Вот (неполированное) решение:

static String highestRepeated(String[] str) {
    String[] sorted = Arrays.copyOf(str, str.length);
    Arrays.sort(sorted, 0, sorted.length, Comparator.reverseOrder());
    String currentString = sorted[0];
    String bestString = sorted[0];
    int maxCount = 1;
    int currentCount = 1;
    for (int i = 1 ; i < sorted.length ; i++) {
        if (currentString.equals(sorted[i])) {
            currentCount++;
        } else {
            if (maxCount < currentCount) {
                maxCount = currentCount;
                bestString = currentString;
            }
            currentString = sorted[i];
            currentCount = 1;
        }
    }
    if (currentCount > maxCount) {
        return currentString;
    }
    return bestString;
}

Пояснение:

Сортировка массива по лексикографически по убыванию. Вот что делает Arrays.sort(sorted, 0, sorted.length, Comparator.reverseOrder());. мы сортируем в этом порядке, потому что вы хотите самую большую строку, если есть несколько строк с одинаковым количеством повторений.

Теперь мы можем просто считать строки, проходя через массив. Нам не нужна хеш-карта или что-то еще, потому что мы знаем, что в остальной части массива не будет больше строки, когда мы встретим другую строку.

currentString - это строка, для которой в данный момент мы рассчитываем количество повторений, используя currentCount. maxCount - это число вхождений самой повторяющейся строки - bestString - которую мы в настоящее время посчитали.

Оператор if довольно понятен: если это та же строка, посчитайте ее, в противном случае посмотрите, не окажется ли предыдущая строка, которую мы посчитали (currentCount), больше, чем текущий максимум.

В конце я проверяю, превышает ли последняя подсчитанная строка максимум. Если последняя строка в массиве окажется самой повторяющейся, bestString не будет назначена ему, потому что bestString назначается только тогда, когда встречается другая строка.

Обратите внимание, что этот алгоритм не обрабатывает граничные случаи, такие как пустые массивы или только одноэлементные массивы. Я уверен, что вы сами это поймете.

Answer 2

другая версия

static String lastMostFrequent(String ... strs) {
    if (strs.length == 0) return null;
    Arrays.sort(strs);
    String str = strs[0];
    for (int longest=0, l=1, i=1; i<strs.length; i++) {
        if (!strs[i-1].equals(strs[i])) { l=1; continue; }
        if (++l < longest) continue;
        longest = l;
        str = strs[i];
    }
    return str;
}

изменение

if (++l <= longest) continue;

для firstMostFrequent

Answer 3

Вы не можете использовать ==, чтобы проверить, совпадают ли две строки. попробуйте использовать это вместо:

if (str[k].equals(str[l])) {
                // if matched, increase count
                num++;
            }