Предложения по оптимизации кода для передачи TLE на Java - PullRequest
Новая
       22

Предложения по оптимизации кода для передачи TLE на Java

0 голосов
/ 20 марта 2019

Я написал код, который принимает два целочисленных массива в качестве входных данных и создает две древовидные карты со своими частотами (число вхождений целых чисел) и записывает значения, которых нет в обеих или в которых частоты различаются, это не проходит тестовый случай, когда размер массива 10 ^ 6 из-за TLE (превышено ограничение по времени). 

import java.util.*;
//import java.util.stream.Collectors;
public class Solution {

public static void main(String args[])
{
    Scanner s = new Scanner(System.in);
    int x=s.nextInt();
    int[] arr=new int[x];
    int i,j,count=0;
    for(i=0;i<x;i++)
    {
    arr[i]=s.nextInt(); 
    }
    Map<Integer, Integer> check=new TreeMap<Integer, Integer>();
    for(i=0;i<x;i++)
    {
        for(j=0;j<x;j++)
        {
            if(arr[i]==arr[j])
            {
                count++;
            }
        }
        check.put(arr[i], count);
        count=0;
    }
    int y=s.nextInt();
    int[] brr=new int[y];
    for(i=0;i<y;i++)
    {
    brr[i]=s.nextInt(); 
    }
    Map<Integer, Integer> check1=new TreeMap<Integer, Integer>();
    int count1=0;
    for(i=0;i<y;i++)
    {
        for(j=0;j<y;j++)
        {
            if(brr[i]==brr[j])
            {
                count1++;
            }
        }
        check1.put(brr[i], count1);
        count1=0;
    }
    //System.out.println(check);
    //System.out.println(check1);
    ArrayList<Integer> store=new ArrayList<Integer>();
    for(int key:check1.keySet())
    {
        if(check.containsKey(key))
        {
            int valb=check.get(key);
            int vala=check1.get(key);
            if(vala-valb!=0)
            {
                store.add(key);
            }
        }
        else
        {
            store.add(key);
        }
    }
    //Collections.sort(store);
    for(i=0;i<store.size();i++)
    {
        System.out.print(store.get(i)+" ");
    }
}

}

1 Ответ

1 голос
/ 20 марта 2019

Вместо того, чтобы проходить по одному и тому же массиву во вложенных циклах (O (n ^ 2) время), вычисляя дубликаты, как это 

    for(i=0;i<x;i++)
    {
        for(j=0;j<x;j++)
        {
            if(arr[i]==arr[j])
            {
                count++;
            }
        }
        check.put(arr[i], count);
        count=0;
    }

Вы можете увеличить значение карты для каждого числа в массиве. Примерно так: 

    for (int item: arr) {
      if (check.containsKey(item)) {
          check.put(item, check.get(item) + 1);
      } else {
          check.put(item, 1);
      }
    }

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

[1, 2, 3, 4, 2, 3, 4, 5]

карта будет выглядеть как 

{1 -> 1, 2 -> 2, 3 -> 2, 4 -> 2, 5 -> 1}

Это также выполняется за O (n), если вы используете HashMap вместо TreeMap.

Для сортировки вывода вы можете использовать TreeSet вместо ArrayList.

...