Здравствуйте, vsb, Вы писали:

vsb>Здравствуйте, samius, Вы писали:

S>>Здравствуйте, vsb, Вы писали:

vsb>>>Здравствуйте, Xobotik, Вы писали:

vsb>>>Если M < N, то вот решение. Не выделяет лишней памяти, не изменяет исходный массив. Печатает одно из чисел, которые повторяются 2 или более раз.
S>>int[] a = { 1, 3, 2, 1, 4 };
S>>выдает 4

vsb>N = 5, M = 5, условие не удовлетворено. В общем цифры надо считать с нуля. Если каждое число в вашем примере уменьшить на единицу, то всё работает.

Вы условие задачи читали? Числа от 1-го до M!

Здравствуйте, samius, Вы писали:

S>Здравствуйте, vsb, Вы писали:

vsb>>Здравствуйте, samius, Вы писали:

S>>>Здравствуйте, vsb, Вы писали:

vsb>>>>Здравствуйте, Xobotik, Вы писали:

vsb>>>>Если M < N, то вот решение. Не выделяет лишней памяти, не изменяет исходный массив. Печатает одно из чисел, которые повторяются 2 или более раз.
S>>>int[] a = { 1, 3, 2, 1, 4 };
S>>>выдает 4

vsb>>N = 5, M = 5, условие не удовлетворено. В общем цифры надо считать с нуля. Если каждое число в вашем примере уменьшить на единицу, то всё работает.

S>Вы условие задачи читали? Числа от 1-го до M!

Не придирайтесь Пусть будут от 0 до M-1, это ничего не изменит, если надо для исходной задачи — просто -1 написать в некоторых местах.

        int[] a = { 1, 5, 1, 4, 3 };
        int i, j;
        
        i = j = a.length - 1;
        do {
            i = a[i] - 1;
            j = a[a[j] - 1] - 1;
        } while (i != j);
        
        j = a.length - 1;
        do {
            i = a[i] - 1;
            j = a[j] - 1;
        } while (i != j);
        
        System.out.println(i + 1);

Вот вариант, для исходного условия.

Здравствуйте, Xobotik, Вы писали:

X>Условие задачи:
X>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно
X>число в этом массиве повторяется два раза. Найти это число за время O(N).

Как то так.

        static int M = int.MaxValue;
        static int BITS = (int)Math.Ceiling(Math.Log(M) / Math.Log(2));

        static void Sort(ref int[] array)
        {
            int[] buffer = new int[array.Length];
            for (int k = 0; k < BITS; ++k)
            {
                int mask = 1 << k;
                int count = 0;
                for (int i = 0; i < array.Length; ++i)
                {
                    if ((array[i] & mask) == 0) ++count;
                }

                int min = 0;
                
                for (int i = 0; i < array.Length; ++i)
                {
                    if ((array[i] & mask) == 0)
                    {
                        buffer[min++] = array[i];
                    }
                    else buffer[count++] = array[i];
                }
                
                int[] temp = array;
                array = buffer;
                buffer = temp;
            }
        }


        static void Main(string[] args)
        {
            int[] arr = new int[] { 5, 7, 2, 111, 4235, 0, 3, 11, 5251254, 9, 7 };
            Sort(ref arr);

            for(int i = 1; i < arr.Length; ++i)
            {
                if (arr[i - 1] == arr[i]) Console.WriteLine(arr[i]);
            }
        }

Требует O(N) дополнительной памяти и вообще говоря выполняется за время O(N * log M). Но в условии не сказано, что log M нельзя считать константой, и решение никак не должно зависеть от M. Полагаю это и не возможно.

Здравствуйте, LaptevVV, Вы писали:

LVV>Здравствуйте, Xobotik, Вы писали:

LVV>Целые числа сортируются за время O(N) поразрядной сортировкой. И все.

Спасибо! Не знал, что есть такая сортировка для целых чисел.

Здравствуйте, Xobotik, Вы писали:

X>Условие задачи:
X>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно
X>число в этом массиве повторяется два раза. Найти это число за время O(N).

using System;
using System.Linq;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main()
        {
            var array = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 14, 15, 16, 17, 18, 19, 20 };
            var duplicate = array.Sum(i => i) - GetProgressionSum(array.Length - 1, 1);

            Console.WriteLine(duplicate);
        }

        static int GetProgressionSum(int length, int step)
        {
            var result = 0;

            for (var i = 1; i <= length; i+=step)
            {
                result += i;
            }

            return result;
        }
    }
}

Здравствуйте, uxio, Вы писали:

U>Здравствуйте, Xobotik, Вы писали:

X>>Условие задачи:
X>>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно
X>>число в этом массиве повторяется два раза. Найти это число за время O(N).

могу на VB

DIM S(M) AS byte
DIM data(N) AS long
' заполняем data
.
.
FOR I = 1 TO N
if S( data(i) ) = 0 then
S( data(i) ) = 1
else
' повтор — ура нашли!
exit for
endif
next
msgbox S( data(i) )

Здравствуйте, Xobotik, Вы писали:

X>Условие задачи:
X>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно
X>число в этом массиве повторяется два раза. Найти это число за время O(N).

Как то лениво искать по всей ветке. Наверное вариант с xor уже звучал, да?

Здравствуйте, lastcross, Вы писали:

L>Здравствуйте, Xobotik, Вы писали:

X>>Условие задачи:
X>>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно
X>>число в этом массиве повторяется два раза. Найти это число за время O(N).

L>Как то лениво искать по всей ветке. Наверное вариант с xor уже звучал, да?
"Слышал звон, да не знает где он"(с)

XOR ищет из повторяющих — одно не повторяющееся, тут задача наоборот

Здравствуйте, elmal, Вы писали:

E>Здравствуйте, samius, Вы писали:

S>>Судя по всему речь о другой задаче, в которой все числа кроме одного встречаются четное число раз.
E>Принцип тот же самый .

Принцип тот же самый?
И ты сходу такое решаешь? Да не гони.
Решал когда-то такую задачку на тестовое задание, но я принцип решения нагуглил.
Вот мой код:

#include "stdafx.h"
#include <algorithm>

using namespace std;
typedef unsigned char BYTE;


//
// Random test array, containing 2 the same numbers.
//

static unsigned test_array[] = 
{
    198, 258, 511, 173, 896, 415, 355, 71, 9012, 8, 15, 174, 886,
    357, 422, 86, 114, 20, 544, 300, 2221, 41, 205, 278, 877, 66,
    431, 30, 5002, 10, 54, 12, 82, 7019, 377, 4, 15906, 511, 123,
    2233, 8018, 11, 20501, 911, 6034, 1111, 4448, 9876, 35461, 9,
    8192,
};

const unsigned NumElementsInTestArray = sizeof( test_array ) / sizeof( unsigned int );


/*
 ******************************************************************************
 *
 * Function Name:           CreateCounters()
 *
 * Function Purpose:        Creates counter arrays.
 *
 * Function Description:    Fill counter arrays with the amount of the numbers 
 *                          in the sorting array (data) with the given byte 
 *                          value for the each byte position.
 * Arguments:
 *      unsigned * data     - [in] Data that are going to be sorted.
 *      unsigned * counters - [out] Counters arrays.
 *      unsigned const N    - [in] Number of elements in the data array.
 *      
 *
 * Return value:            None.
 *
 * Revision History:
 *
 *      03/02/2009:         Created.
 *
 ******************************************************************************
*/
static void CreateCounters( unsigned * data, unsigned * counters, unsigned const N )
{
    //
    // Counters array number i is placed at address ( counters + 256 * i )
    //
    
    memset(
        counters, 
        0, 
        256 * sizeof( unsigned ) * sizeof( long )
        ); 
    
    BYTE * pb    = ( BYTE* ) data;
    BYTE * pbEnd = ( BYTE* )( data + N );

    while( pb != pbEnd )
    {
        for( int i = 0; i < sizeof( unsigned ); i++, pb++ )
        {
            counters[ 256 * i + *pb ] ++ ;
        }
    }
}


/*
 ******************************************************************************
 *
 * Function Name:           RadixPass()
 *
 * Function Purpose:        One pass and sort for the given key position.
 *
 * Function Description:    
 *
 * Arguments:
 *      int          offset  - [in]  Key (byte) position (0..3);
 *      const long   N       - [in]  Size of sorting array .
 *      unsigned *   inArr   - [in]  Sorting array.
 *      unsigned *   outArr  - [out] Resulting array.
 *      unsigned *   cntrArr - [in]  Array of counters.
 *      
 *
 * Return value:            None.
 *
 * Revision History:
 *
 *      03/02/2009:         Created.
 *
 ******************************************************************************
*/
static void RadixPass( int          offset, 
                       const long   N, 
                       unsigned *   inArr, 
                       unsigned *   outArr, 
                       unsigned *   cntrArr )
{
    unsigned long sum = 0;
    unsigned long tmp;
    
    unsigned * pCntrArr             = cntrArr;
    const unsigned * const cntrEnd  = cntrArr + 256;

    for( ; pCntrArr != cntrEnd; pCntrArr++ )
    {
        tmp         = *pCntrArr;
        *pCntrArr   = sum;
        sum        += tmp;
    }
    
    BYTE * pb = ( BYTE* )inArr + offset;
    unsigned * pInArr = inArr;
    
    for( int i = 0; i < N; i++, pb += sizeof( unsigned ), pInArr++ )
    {
        unsigned * pc = cntrArr + *pb;
        outArr[ *pc ] = *pInArr;
        ( *pc )++;
    }
}


/*
 ******************************************************************************
 *
 * Function Name:           RadixSort()
 *
 * Function Purpose:        Sorts array of unsigned integers. 
 *
 * Function Description:    Sort array of unsigned number by Radix Sort method.
 *                          Bytes of the number are used as sorting keys.
 *
 * Arguments:               unsigned * &inArr [in out] - 
 *                          Reference to pointer to source array.
 *
 *                          const long N [in] - Array size.
 *      
 *
 * Return value:            None.
 *
 * Revision History:
 *
 *      03/02/2009:         Created.
 *
 ******************************************************************************
*/
void RadixSort( unsigned * &inArr, const long N )
{
    //
    // One-dimension array is used for counters. 
    // Byte values is used as counter array index. Each element of counter 
    // array contains total amount of numbers with the given value of the byte.
    // For each byte position (0,1,2,3) exists separate counters array.
    // 
    // Placement counters in memory:
    // -----------------------------------------------------------------------------
    //  0s counters array  |  1st cntrs. arr.  |  2nd cntrs. arr. |  3rd cntrs. arr.
    // -----------------------------------------------------------------------------
    //   [0]                [256]               [512]              [768]
    //
    
    unsigned counters[ sizeof( unsigned ) * 256 ];
    unsigned * outArr = new unsigned[ N ];
    
    CreateCounters( 
        inArr, 
        counters, 
        N 
        );
    
    int swapCounter = 0;    // need due to optimization

    for( int i = 0; i < sizeof( unsigned ); i++ )
    {
        unsigned * cntrsArr = counters + 256 * i;
        
        //
        // A little optimization: if all bytes in the current position are the same
        // (equal to zero), sorting by this position is not required.
        //

        if( N == counters[ 0 ] )
        {
            continue;
        }

        RadixPass(
            i, 
            N, 
            inArr, 
            outArr, 
            cntrsArr
            );

        swap( 
            inArr, 
            outArr 
            );

        swapCounter ++ ;
    }
    
    //
    // Do not forget restore pointer to the incoming array if the number of swaps were odd !
    //

    if( swapCounter & 1 )
    {
        swap( 
            inArr, 
            outArr 
            );
    }

    delete [] outArr;
}


//
// Application entry point.
//

int main( int argc, char * argv[] )
{
    unsigned * pArr = test_array;
    unsigned dupNum = 0;
    
    printf( "Original array:\n" );

    for( int i = 1; i < NumElementsInTestArray; i++ )
    {
        printf( "%6d ", test_array[ i ] );
        
        if( !( i % 10 ))
        {
            printf( "\n" );
        }
    }

    RadixSort( 
        pArr, 
        NumElementsInTestArray 
        );
    
    printf( "\n\nSorted array:\n" );

    for( int i = 1; i < NumElementsInTestArray; i++ )
    {
        printf( "%6d ", test_array[ i ] );
        
        if( !( i % 10 ))
        {
            printf( "\n" );
        }

        if( test_array[ i - 1 ] == test_array[ i ] )
        {
            dupNum = test_array[ i ];
        }
    }
    
    printf(
        "\n\n"
        "Dublicate number found: %d\n",
        dupNum
        );

    _getch();

    return 0;
}

Здравствуйте, batu, Вы писали:

B>Здравствуйте, Xobotik, Вы писали:

X>>Здравствуйте, Don Reba, Вы писали:

DR>>>Здравствуйте, batu, Вы писали:

B>>>>В среднем O(3N/2) что явно лучше чем O(N)

DR>>>Несколько замечаний:

DR>>>1. 3N/2 > N
DR>>>2. O(3N/2) = O(N)
DR>>>3. Сложность алгоритма не О(N), а O(M), что может быть гораздо хуже.

X>>Отлично, ну а как тогда реализовывать поставленную задача, если алгоритм должен быть без сравнения и перебора элементов во вспомогательном массиве (так же без сравнения во входном массиве) за время O(N). Может быть в задаче, то и имелось ввиду за O(M).
B>Видимо алгоритм не понят.
B>Мы резервируем массив размером с диапазон значений, и в цикле заносим единицу по индексу значения этого числа.

Зачем ребенка неправильно учишь?
Ну зарезервируй массив с диапазоном значений 4 миллиарда. "Офигенное" решение.

ЗЫ. А еще в условии не сказано, что числа положительные.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, samius, Вы писали:

S>>Здравствуйте, -VladK-, Вы писали:

VK>>>Народ, да вы че?
VK>>>сколько уже прочитал вариантов и некто не догадался просто просуммировать массив и сравнить с суммой арифметической прогрессии ?!

S>>Разве в условии сказано что N = M + 1?
S>>N = 10, M = 1000. Куда приложить прогрессию?

А>"Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно
А>число в этом массиве повторяется два раза." Раз повторяется одно число, значит N = M + 1.

N в общем случае не равняется M + 1, не? Намекаю другими словами, что в условии не сказано, что в массиве встечается каждое число от 1 до М.
Пример:

int a[] = { 1, 100000, 1, 3 };

Здравствуйте, Аноним, Вы писали:

А>Тогда нужно уточнение условия.

Не нужно.

Здравствуйте, opener, Вы писали:

B>>Мы резервируем массив размером с диапазон значений, и в цикле заносим единицу по индексу значения этого числа.

O>Зачем ребенка неправильно учишь?
O>Ну зарезервируй массив с диапазоном значений 4 миллиарда. "Офигенное" решение.

O>ЗЫ. А еще в условии не сказано, что числа положительные.
Так ребенок должен малость соображать, что это не для такого случая

Здравствуйте, batu, Вы писали:

B>Здравствуйте, opener, Вы писали:

B>>>Мы резервируем массив размером с диапазон значений, и в цикле заносим единицу по индексу значения этого числа.

O>>Зачем ребенка неправильно учишь?
O>>Ну зарезервируй массив с диапазоном значений 4 миллиарда. "Офигенное" решение.

O>>ЗЫ. А еще в условии не сказано, что числа положительные.
B>Так ребенок должен малость соображать, что это не для такого случая

Дык ты ж ему изначально советуешь неправильно. Ты же для него гуру, твое мнение изначально авторитетное.

Здравствуйте, opener, Вы писали:

O>Дык ты ж ему изначально советуешь неправильно. Ты же для него гуру, твое мнение изначально авторитетное.
Насчет гуру и авторитетов то лестно.. но херня.. А насчет правильно-не правильно.. это зависит от реальной задачи..

Здравствуйте, batu, Вы писали:

B>Здравствуйте, opener, Вы писали:

O>>Дык ты ж ему изначально советуешь неправильно. Ты же для него гуру, твое мнение изначально авторитетное.
B>Насчет гуру и авторитетов то лестно.. но херня.. А насчет правильно-не правильно.. это зависит от реальной задачи..

B>Мы резервируем массив размером с диапазон значений, и в цикле заносим единицу по индексу значения этого числа.

Твой совет? )
А теперь выполни его для такого массива:

unsigned arr[] = { 1, 2, 3, 0xFFFFFFFF };

Здравствуйте, opener, Вы писали:

O>Здравствуйте, batu, Вы писали:

B>>Здравствуйте, opener, Вы писали:

O>>>Дык ты ж ему изначально советуешь неправильно. Ты же для него гуру, твое мнение изначально авторитетное.
B>>Насчет гуру и авторитетов то лестно.. но херня.. А насчет правильно-не правильно.. это зависит от реальной задачи..

B>>Мы резервируем массив размером с диапазон значений, и в цикле заносим единицу по индексу значения этого числа.

O>Твой совет? )
O>А теперь выполни его для такого массива:

O>

O>unsigned arr[] = { 1, 2, 3, 0xFFFFFFFF };
O>

Та запросто. Сначала пронумеровать, и выполнить тоже самое с номерами.

Здравствуйте, batu, Вы писали:

B>Здравствуйте, opener, Вы писали:

O>>

O>>unsigned arr[] = { 1, 2, 3, 0xFFFFFFFF };
O>>

B>Та запросто. Сначала пронумеровать, и выполнить тоже самое с номерами.
Зачем выполнять то же самое, если в процессе нумерации решение уже будет найдено?

Здравствуйте, samius, Вы писали:

S>Здравствуйте, batu, Вы писали:

B>>Здравствуйте, opener, Вы писали:

O>>>

O>>>unsigned arr[] = { 1, 2, 3, 0xFFFFFFFF };
O>>>

B>>Та запросто. Сначала пронумеровать, и выполнить тоже самое с номерами.
S>Зачем выполнять то же самое, если в процессе нумерации решение уже будет найдено?

Еще один зачетный совет от гуру.

Здравствуйте, samius, Вы писали:

S>Здравствуйте, batu, Вы писали:

B>>Здравствуйте, opener, Вы писали:

O>>>

O>>>unsigned arr[] = { 1, 2, 3, 0xFFFFFFFF };
O>>>

B>>Та запросто. Сначала пронумеровать, и выполнить тоже самое с номерами.
S>Зачем выполнять то же самое, если в процессе нумерации решение уже будет найдено?
Есть и такой вариант. Смотря как задача поставлена