Durchfahren eines großen Arrays

Question

Ein Array hat Elemente (1,2,2,1,1). Ich muss feststellen, dass die Anzahl der verschiedenen Elemente in dem Unterfeld gleich der Anzahl der verschiedenen Elemente in dem gegebenen Array sein sollte, d. H. Die Anzahl der distinkten Elemente in dem Array ist (1 und 2).

Alle möglichen Subarrays sind [1,2], [1,3], [1,4], [1,5], [2,4], [2,5], [3,4] , [3,5]

Eindeutig bedeutet keine eindeutigen Elemente es 2 {1,2,2} hat 2 verschiedene Elemente. In dieser Frage bedeutet 1,4 nicht, dass wir 1. Element und 4. Element einschließen, dh unser Unterfeld beginnt bei 1 und endet bei 4 , daher ist Unterfeld [1,2,2,1], das 2 verschiedene Elemente hat und es erfüllt, da das ganze Array 2 verschiedene Elemente hat.

Das Problem der que ist, dass ich Testfall von Array-Größe von 2 Lacs bekomme und ich muss die Ausgabe in 1 Sekunde und jedes Mal bekomme ich Zeitlimit überschreiten auftritt.

Nachdem ich die Antwort gesehen habe, muss ich Pufferleser (anstelle von Scanner {wegen Leistungsproblem}) und hashmap verwenden.

Zuerst benutzte ich Scanner und Pufferleser und beide gaben Ausgabe in 2 Minuten 17sec (für 2 Lac Eingabe). Warum also muss ein Pufferleser verwendet werden (mit dem Scanner wurde die Länge des Codes reduziert).

Zweitens i getestet sowohl den Code auf der Website und sowohl der Code gab Ausgang innerhalb von 1 Sekunde, während in meinem lokalen Rechner es 2 min 17 sec dauerte. Ich habe nicht verstanden, warum es so viel Unterschied gibt.

Drittens, was ist die Bedeutung dieses Codes: final int mod = (int) 1e9 + 7; (obwohl ich oft gesehen habe, wenn große Zahl verwendet)

Viertens, was ist der Gebrauch des folgenden Codes mit dem gepufferten Leser verwendet.

Ich bin Anfänger in Java so pls gibt einfache Antwort und sorry für den langen Post

class InputReader 
{ 
private InputStream stream; 
private byte[] buf = new byte[1024]; 
private int curChar; 
private int numChars; 
private SpaceCharFilter filter; 

public InputReader(InputStream stream) 
{ 
    this.stream = stream; 
} 

public int read() 
{ 
    if (numChars == -1) 
     throw new InputMismatchException(); 
    if (curChar >= numChars) 
    { 
     curChar = 0; 
     try 
     { 
      numChars = stream.read(buf); 
     } catch (IOException e) 
     { 
      throw new InputMismatchException(); 
     } 
     if (numChars <= 0) 
      return -1; 
    } 
    return buf[curChar++]; 
} 

public int readInt() 
{ 
    int c = read(); 
    while (isSpaceChar(c)) 
     c = read(); 
    int sgn = 1; 
    if (c == '-') 
    { 
     sgn = -1; 
     c = read(); 
    } 
    int res = 0; 
    do 
    { 
     if (c < '0' || c > '9') 
      throw new InputMismatchException(); 
     res *= 10; 
     res += c - '0'; 
     c = read(); 
    } while (!isSpaceChar(c)); 
    return res * sgn; 
} 

public String readString() 
{ 
    int c = read(); 
    while (isSpaceChar(c)) 
     c = read(); 
    StringBuilder res = new StringBuilder(); 
    do 
    { 
     res.appendCodePoint(c); 
     c = read(); 
    } while (!isSpaceChar(c)); 
    return res.toString(); 
} 
public double readDouble() { 
    int c = read(); 
    while (isSpaceChar(c)) 
     c = read(); 
    int sgn = 1; 
    if (c == '-') { 
     sgn = -1; 
     c = read(); 
    } 
    double res = 0; 
    while (!isSpaceChar(c) && c != '.') { 
     if (c == 'e' || c == 'E') 
      return res * Math.pow(10, readInt()); 
     if (c < '0' || c > '9') 
      throw new InputMismatchException(); 
     res *= 10; 
     res += c - '0'; 
     c = read(); 
    } 
    if (c == '.') { 
     c = read(); 
     double m = 1; 
     while (!isSpaceChar(c)) { 
      if (c == 'e' || c == 'E') 
       return res * Math.pow(10, readInt()); 
      if (c < '0' || c > '9') 
       throw new InputMismatchException(); 
      m /= 10; 
      res += (c - '0') * m; 
      c = read(); 
     } 
    } 
    return res * sgn; 
} 
public long readLong() { 
    int c = read(); 
    while (isSpaceChar(c)) 
     c = read(); 
    int sgn = 1; 
    if (c == '-') { 
     sgn = -1; 
     c = read(); 
    } 
    long res = 0; 
    do { 
     if (c < '0' || c > '9') 
      throw new InputMismatchException(); 
     res *= 10; 
     res += c - '0'; 
     c = read(); 
    } while (!isSpaceChar(c)); 
    return res * sgn; 
} 
public boolean isSpaceChar(int c) 
{ 
    if (filter != null) 
     return filter.isSpaceChar(c); 
    return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; 
} 

public String next() 
{ 
    return readString(); 
} 

public interface SpaceCharFilter 
{ 
    public boolean isSpaceChar(int ch); 
} 
} 

class OutputWriter 
{ 
private PrintWriter writer; 

public OutputWriter(OutputStream outputStream) 
{ 
    writer = new PrintWriter(new BufferedWriter(new  OutputStreamWriter(outputStream))); 
} 

public OutputWriter(Writer writer) 
{ 
    this.writer = new PrintWriter(writer); 
} 

public void print(Object... objects) 
{ 
    for (int i = 0; i < objects.length; i++) 
    { 
     if (i != 0) 
      writer.print(' '); 
     writer.print(objects[i]); 
    } 
} 

public void printLine(Object... objects) 
{ 
    print(objects); 
    writer.println(); 
} 

public void close() 
{ 
    writer.close(); 
} 

public void flush() 
{ 
    writer.flush(); 
} 
} 

Answer 1

Antwort auf Ihre vierte Abfrage: Der Code ist schneller als normale Scanner-Klasse. Daher können Sie es in Coding-Wettbewerben verwenden. Ich habe den folgenden Code auf eine ~ 55 MB Textdatei "test.txt" verwendet.

package so; 

import java.io.File; 
import java.io.FileInputStream; 
import java.io.IOException; 
import java.util.Scanner; 

public class UseIR { 
public static void main(String[] args) throws IOException { 

//checked using the class provided 'InputReader' 
InputReader ob=new InputReader(new FileInputStream(new File("src\\so\\test.txt"))); 
long str=0; 
StringBuilder sb=new StringBuilder(); 
long curTime=System.currentTimeMillis(); 
while((str=ob.read())!=-1){ 
    sb.append(((char)str)); 
} 
System.out.println("done "+(System.currentTimeMillis()-curTime)); 

//checked using the Scanner class 

curTime=System.currentTimeMillis(); 
Scanner s=new Scanner(new File("src\\so\\test.txt")); 
sb=new StringBuilder(); 
while(s.hasNext()){ 
    sb.append(s.next()); 
} 
System.out.println("done "+(System.currentTimeMillis()-curTime)); 
} 
} 

Mit dem folgenden Ausgang:

done 447 
done 2061 

Hoffe, es hilft :)