Zeit Komplexität von verschachtelten While-Schleifen?

Question

Ich mache eine Interviewvorbereitung Frage, wo ich Zeiten hinzufügen muss, die mir in Bezug auf eine Reihe von Zeiten gegeben sind. Ich habe zwei Loops, einen um die Zeiten zu analysieren und einen um die Minuten von den Sekunden zu trennen. Die zwei verschachtelten Schleifen machen, glaube ich, die Zeitkomplexität O (n^2). Meine Mitbewohner sagen mir, dass dies ein schrecklicher Code ist und in O (n) Zeit gelöst werden kann, aber ich kann nicht herausfinden, wie. Jede Hilfe wäre willkommen. Danke im Voraus. Unten ist mein Code für dieses Problem.

import java.io.*; 
import java.util.*; 

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

String x = "12:32 34:01 15:23 9:27 55:22 25:56"; 

String[] time = new String[6]; 
int[] mins = new int[6]; 
int[] secs = new int[6]; 
int hourTotal = 0; 
int minTotal = 0; 
int secTotal = 0; 

Scanner scan = new Scanner(x); 
scan.useDelimiter(" "); 

int i = 0; 
while(scan.hasNext() == true){ 

    time[i] = scan.next(); 
    Scanner scanz = new Scanner(time[i]); 
    scanz.useDelimiter(":"); 

    int diff = 0; 
    while(scanz.hasNext() == true){ 
    mins[i] = scanz.nextInt(); 
    secs[i] = scanz.nextInt(); 

    minTotal = minTotal + mins[i]; 
    secTotal = secTotal + secs[i]; 
    } 
    while(secTotal >= 60){ 
    if(secTotal >= 60){ 
     secTotal = secTotal - 60; 
     minTotal++; 
    } 
    } 
    while(minTotal >= 60){ 
    if(minTotal >= 60){ 
     minTotal = minTotal - 60; 
     hourTotal++; 
    } 
    } 
} 
i++; 

System.out.print(hourTotal + ":" + minTotal + ":" + secTotal); 
    } 
} 

Answer 1

Ich würde hier die Verwendung der split Methode machen. Der folgende Code wird in O (n) Zeit ausgeführt, glaube ich.

class Time { 
    public static void main(String[] args) { 
    String x = "12:32 34:01 15:23 9:27 55:22 25:56"; 

    String[] time = x.split(" "); 
    int hourTotal = 0; 
    int minuteTotal = 0; 
    int secondTotal = 0; 

    String[] timeBreakdown; 
    for (int i = 0; i < time.length ; i++) { 
     timeBreakdown = time[i].split(":"); 
     minuteTotal = minuteTotal + Integer.parseInt(timeBreakdown[0]); 
     secondTotal = secondTotal + Integer.parseInt(timeBreakdown[1]); 

     if (secondTotal >= 60) { 
     minuteTotal++; 
     secondTotal = secondTotal - 60; 
     } 
     if (minuteTotal >= 60) { 
     hourTotal++; 
     minuteTotal = minuteTotal - 60; 
     } 
    } 

    System.out.println(hourTotal + ":" + minuteTotal + ":" + secondTotal); 
    } 
} 

Answer 2

public static void main(String[] args) { 
    String x = "12:32 34:01 15:23 9:27 55:22 25:56"; 
    String[] minuteSecondPairs = x.split(" "); 
    int totalMinute = Arrays.stream(minuteSecondPairs) 
          .mapToInt(pair -> Integer.parseInt(pair.split(":")[0])) 
          .sum(); 
    int totalSecond = Arrays.stream(minuteSecondPairs) 
          .mapToInt(pair -> Integer.parseInt(pair.split(":")[1])) 
          .sum(); 
    int remainingSecond = totalSecond % 60; 
    totalMinute += (totalSecond - remainingSecond)/60; 
    System.out.println("Total hours: " + Math.floor(totalMinute/60) + " | Total minute: " + (totalMinute % 60) + " | Total second: " + remainingSecond); 
} 

Dieses in O läuft (n)