Обход большого массива

Question

Массив имеет элементы (1,2,2,1,1). Я должен найти, что количество отдельных элементов в вспомогательном массиве должно быть равно числу отдельных элементов в данном массиве. I число различных элементов элементов в массиве (1 и 2).

Все возможные подмассивы: [1,2], [1,3], [1,4], [1,5], [2,4], [2,5], [3,4] , [3,5]

Distinct означает, что нет отдельных элементов it 2 {1,2,2} имеет 2 отдельных элемента. В этом вопросе 1,4 не означает, что мы включаем 1-й элемент и 4-й элемент, это означает, что наш вспомогательный массив начинается с 1 и заканчивается на 4 , таким образом, вспомогательный массив равен [1,2,2,1], который имеет 2 отдельных элемента и он удовлетворяет, поскольку весь массив имеет 2 разных элемента.

Проблема в том, что я получил тестовый пример размер массива из 2 lacs, и я должен получить выход за 1 секунду, и каждый раз, когда я получаю превышение лимита времени.

После просмотра ответа я должен использовать буферный считыватель (вместо сканера {из-за проблемы с производительностью}) и hashmap.

Во-первых, я использовал сканер и буферный считыватель, и оба дали выход в течение 2 минут 17 секунд (для входа 2 лака). Итак, зачем нужно использовать буферизатор (с помощью сканера уменьшена длина кода).

Во-вторых, я проверил и код на сайте, и оба кода дали результат в течение 1 секунды, тогда как на моей локальной машине это заняло 2 мин. 17 сек. я не понимал, почему так много разницы.

В-третьих, в чем смысл этого кода: final int mod = (int) 1e9 + 7; (хотя я видел много раз при использовании большого количества)

В-четвертых, что используется нижеприведенным кодом, используемым с буферизованным считывателем.

Я новичок в Java, так пожалуйста дайте простой ответ и извините за длинный пост

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

ответа на свой четвертый Запрос: Код быстрее, чем при использовании обычного класса сканера. Следовательно, вы можете использовать его в соревнованиях по кодированию. Я использовал следующий код в текстовом файле ~ test.txt объемом ~ 55 МБ.

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)); 
} 
} 

следующих выходными:

done 447 
done 2061 

Надеется, что это помогает :)