Trovare il numero totale di subarray da una data serie di numeri con elementi uguali. Approccio migliore

Question

Trovare il numero totale di subarray da una data serie di numeri con elementi uguali. Approccio migliore

#1 da (2 voti)
#2 da (0 voti)

2

Dato un array di numeri, conta il numero totale di sottoarray (elementi consecutivi) in cui tutti gli elementi sono uguali.

Esempio: per sotto l'array

[1,1,3]

Ans: 4

Di seguito sono riportati i sottoarray desiderati:

[1], [1], [3], [1,1]

Quindi ho scritto per la prima volta un programma Java la cui efficienza è negativa:

import java.util.*;


public class EqualSubarrays {

    public static void main(String[] args) {

        int count = 0;

        Integer[] arr = {1,1,3};
        List<Integer> list = new ArrayList<Integer>(Arrays.asList(arr));
        for(int i=1; i<=arr.length; i++) {
            for(int j=0; j<=arr.length-i; j++) {
                if(areAllElementsEqual(list.subList(j, j+i)))
                    count++;
            }
        }

        System.out.println(count);
    }

    static boolean areAllElementsEqual(List<Integer> list) {
        if (list.size()==1)
            return true;
        if (Collections.frequency(list, list.get(0))==list.size())
            return true;
        else
            return false;
    }

}

E poi, ci ho pensato con più semplicità e ho scritto un programma in Python (comunque può essere scritto in qualsiasi lingua). Eccolo:

def count_equal_subarrays(nums):
    n = len(nums)
    total = 0
    i = 0
    while i < n:
        count = 1
        while i+1 < n and nums[i] == nums[i+1]:
            i += 1
            count += 1
        i += 1
        total += count * (count + 1) / 2

    return int(total)

num_arr = [1, 1, 1, 1]
print(count_equal_subarrays(num_arr))

Volevo sapere se esiste un metodo più efficiente o un approccio interessante. Se lo sai, per favore spiega pure se è complicato.

java python algorithms

posta xploreraj 08.08.2016 - 22:03

fonte

2 risposte

Leggi altre domande sui tag java python algorithms

Etichettatura delle molteplicità nelle mappature delle tabelle di classi Proprietà delle funzioni con lo stesso input = output indipendente dalla lingua o dai nomi

score 2 · Answer 1

In primo luogo il tuo modo di formulare la domanda è strano, min e max sono gli stessi. Questo ovviamente significa solo che tutti gli elementi nel sottoarray sono uguali.

Una volta che hai una matrice di tutti gli elementi uguali, se questa ha lunghezza n allora può avere n (n + 1) / 2 sottoarray.

Ad esempio [1,1,1] può avere [1], [1], [1], [1,1], [1,1], [1,1,1] e 3 (3+ 1) / = 6

Quindi tutto quello che dovrebbe essere il tuo algoritmo è passare attraverso l'array mantenendo la memoria di ciò che era l'elemento precedente e di quanti di una fila di quell'elemento è stato. Se è lo stesso, riponi l'importo e continua. Una volta è diverso l'importo che hai inserito nella formula n (n + 1) / 2 e lo aggiungi al totale.

Il tutto quindi può essere fatto in O (n), non c'è bisogno di un doppio ciclo

score 0 · Answer 2

Sto scrivendo l'algoritmo, puoi implementarlo in qualsiasi lingua desideri

Algoritmo: matrice A = {1,3,1} 1. prima di tutto ordina il tuo array i.e array A = {1,1,3} 2. crea un dizionario / array di conteggio di ogni elemento univoco dell'array

Count{ 
Element   count
 1          2
 3          1

}

quindi applica la formula (n * (n + 1)) / 2 per ogni valore di Count [elemento] e aggiungi tutti i valori. Questa è la tua risposta per Count [1] il conteggio è 2 quindi (2 * (2 + 1)) / 2 = 3 Per conteggio [3] il conteggio è 1 quindi (1 * (1 + 1)) / 2 = 1 Aggiungendo tutti loro 3 + 1 = 4 rispondi se hai dei dubbi
- Se stai utilizzando una matrice, cerca l'elemento massimo dell'array, quindi crea un array di conteggio di quella dimensione