Код Вопрос об объединении

Question

Запишите функцию: int solution (int K, int A [], int N); , что, учитывая целое число K и непустой нуль-индексированный массив A из N целых чисел, возвращает количество ограниченных_средств массива A. Если число ограниченных_средств превышает 1,000,000,000, функция должна вернуть 1,000,000,000. Например, если: А [0] = 3 А [1] = 5 А [2] = 7 А [3] = 6 А [4] = 3 функция должна возвращать 9, как объяснено выше. Предположим, что: • N - целое число в диапазоне [1..100.000]; • K - целое число в диапазоне [0,1,000,000,000]; • каждый элемент массива A является целым числом в диапазоне [-1,000,000,000..1,000,000,000]. Сложность: • ожидаемая наихудшая временная сложность - O (N); • ожидаемая наихудшая сложность пространства - это O (N), за пределами хранения ввода (не считая хранения, необходимого для входных аргументов). */

мой код не работает в O (N), и я хочу, любое предложение ?? import java.util.ArrayList;

общественного класса Решение {

/** 
* @param args 
*/ 

public int solution(int K, int[] A) 
{ 
    int numberOfSlices=0; 
    ArrayList<Integer>listOfSlices=new ArrayList<Integer>(); 
    for(int i=0;i<A.length;i++) 
    { 
     for(int j=0;j<A.length;j++) 
     { 
      if((!listOfSlices.contains(A[i]) 
       &&!listOfSlices.contains(A[j]))&&(max(A[i],A[j])-min(A[i],A[j]))<=K) 
      { 
       numberOfSlices++; 

      } 
     } 
      listOfSlices.add(A[i]); 
    } 



    return numberOfSlices; 

} 

/* return the max between two numbers */ 
public int max(int p,int q) 
{ 
    if(p>q) 
    { 
     return p; 
    } 
    else 
    { 
     return q; 
    } 

} 

/*return the min between two numbers */ 
public int min(int p,int q) 
{ 
    if(p<q) 
    { 
     return p; 
    } 
    else 
    { 
     return q; 
    } 

} 
public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    Solution solution=new Solution(); 
    int[] array={3,5,7,6,3}; 
    System.out.println("the number of slices in the array is "+solution.solution(2, array)); 

} 

}

Answer 1

Этот вопрос все еще активен, так что никто не будет давать слишком много, но я укажу вам в правильном направлении (или, по крайней мере, от неправильное направление).

Вложение в петли сопряжено с риском; как есть, вы в основном гарантируете O (N^2). Вам нужно найти способ уменьшить ваш пул, а не повторять снова для каждого элемента.

Тем не менее, поскольку у вас есть это, это приведет к сбою многих тестовых случаев. Если грубая сила терпит неудачу, это означает, что вам не хватает способа обработать corner cases. как проблема предупреждает в полном описании.

Итак:

1) признать, что перебирая экспоненциально медленнее, чем требуется, думать о том, как вы могли бы уменьшить то, что вам нужно искать.

2) Выпишите некоторые сумасшедшие тестовые примеры и найдите где и почему ваш код не удался, а затем передумайте свое решение. Ответ не будет утверждением if для каждого случая.

Ваш код определенно не работает (6, [4, 5, 8, 5, 1, 4, 6, 8, 7, 2, 2, 5]), который должен возвращать 44. Рассмотрим этот тестовый пример.

Удачи.