Кухня(); Задание N38.

участников

Правила [Одномерные массивы] 38. Дана последовательность целых чисел a1, a2, ..., аn. Указать пары чисел аi, аj, таких, что аi + аj = m.

Комментарии (7)

популярные
новые
старые

Для того, чтобы оставить комментарий Вы должны авторизоваться

Vash_the_Stampede

Уровень 11

6 сентября 2014, 15:48

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

public class Main {

    public static void main(String[] args) {
        int[] arr = { 0, 1, 2, 3, 4, 5, 6 };
		Pair[] res = solve(arr, 6);
		System.out.println(Arrays.toString(res));
    }
	
	public static Pair[] solve(int[] arr, int m) {
	    int count = 0;
		int n = arr.length;
		for (int i = 0; i < n; i++) {
			for (int j = i; j < n; j++) {
				if (arr[i] + arr[j] == m) {
					count++;
				}
			}
		}
		
		Pair[] res = new Pair[count];
		for (int i = 0; i < n; i++) {
			for (int j = i; j < n; j++) {
				if (arr[i] + arr[j] == m) {
					res[--count] = new Pair(arr[i], arr[j]);
				}
			}
		}
		return res;
    }
	
	public static class Pair {
		public int first, second;
		
		public Pair(int first, int second) {
			this.first = first;
			this.second = second;
		}

		@Override
		public String toString() {
			return new StringBuffer().append('(').append(first).append(", ").append(second).append(')').toString();
		} 
	}

}

aiv

Уровень 27

7 сентября 2014, 19:05

По-моему второй цикл не нужен, можно в первом в ArrayList сразу добавлять пары. В этом коде два цикла проходят по-очереди по одним и тем же значениям и проверяют их на соответствие одному условию.
К сожалению, сейчас в поездке, компа под рукой нет, написать и проверить код не могу. На планшете еще не научился этого делать :-(.
Кстати, если кто знает какое-нибудь приложение, в котором можно писать код на яблоке, напишете plz.

Vash_the_Stampede

Уровень 11

7 сентября 2014, 19:38

ну, мне нужно сначала узнать размер нового массива. Не нужно предлагать листы, они при необходимости будут инициализировать новый массив и копировать данные(что может повторяться не один раз), что может сделать выгодным заранее вычислить необходимый размер массива. Как вариант, можно заранее объявить массив размером n * n(максимальное количество пар), одним циклом посчитать и записать в массив. А потом еще одним циклом скопировать в новый массив уже необходимого размера. Но тоже 2 цикла получается

aiv

Уровень 27

7 сентября 2014, 20:02

Если вопрос с листами связан с быстродействием, то еще неизвестно, что быстрее отработает, двойной проход по массиву или системная функция копирования массива, если не хватит места для добавления нового элемента.
Второй вариант можно копировать в новый массив системной функцией копирования arraycopy, должно работать быстрее, чем перебором элементов в цикле. Правда, в этом случае в первом цикле, элементы обязательно надо записывать с начала массива.

Vash_the_Stampede

Уровень 11

7 сентября 2014, 20:20

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

aiv

Уровень 27

8 сентября 2014, 09:10

Можно, только пока не могу — в отъезде, еще примерно неделю, может меньше, компа не будет рядом.

aiv

Уровень 27

12 сентября 2014, 21:05

Попробовал тестить так:

package com.javarush.test.Для_ввода_текста;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

public class Solution
{
    public static void main(String[] args) {
        Random rnd = new Random();

        int arrLength = 10000;
        int[] arr = new int[arrLength];

        int m;

        Pair[] resArray;
        ArrayList<Pair> resList;
        long start, end;

        System.out.println("Последовательные числа.");

        // Заполняем массив последовательными числами
        m = arr.length;
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i;
        }

        start = System.currentTimeMillis();
        resArray = solveArray(arr, m);
        end = System.currentTimeMillis();
        System.out.println("Время работы array: " + (end - start) + " мс");
// Вывод закомментирован, потому что очень длительный по времени получается.
// На маленьких массивах можно раскомментировать.
//        System.out.println(Arrays.toString(resArray));

        start = System.currentTimeMillis();
        resArray = solveCopy(arr, m);
        end = System.currentTimeMillis();
        System.out.println("Время работы copy: " + (end - start) + " мс");
//        System.out.println(Arrays.toString(resArray));

        start = System.currentTimeMillis();
        resList = solveList(arr, m);
        end = System.currentTimeMillis();
        System.out.println("Время работы list: " + (end - start) + " мс");
//        System.out.println(resList.toString());

        System.out.println("**********************************");
        System.out.println("Случайные числа.");

        // Заполняем массив случайными числами. Число m взято поменьше,
        // чтобы совпадений было больше.
        m = 50;
        for (int i = 0; i < ar