題目一：找出數(shù)組中重復(fù)的數(shù)字
在一個長度為n的數(shù)組里所有數(shù)字都在0~n-1的范圍內(nèi)，數(shù)組中某些數(shù)字是重復(fù)的，單不知道有幾個重復(fù)數(shù)字，也不知道每個數(shù)字重復(fù)了幾次，請找出數(shù)組中任意的數(shù)字，例如長度為7的數(shù)組{2，3，1，0，2，5，3}，那么對應(yīng)的重復(fù)數(shù)字2或者3

因?yàn)閿?shù)字不重復(fù)而且在0~n-1內(nèi)，所以解題精髓就是用數(shù)組把內(nèi)容插入到數(shù)組坐標(biāo)的相應(yīng)位置，然后比對 如果發(fā)現(xiàn)該數(shù)字在數(shù)組坐標(biāo)位置相同則代表有重復(fù)。

官方demo

//
//  main.cpp
//  數(shù)組中找重復(fù)
//
//  Created by 張傳奇 on 2018/8/1.
//  Copyright ? 2018年 張傳奇. All rights reserved.
//

#include <iostream>

bool duplicate(int numbers[],int length,int * duplication) {
    
    if (numbers == nullptr || length <= 0) {
        return false;
    }
    
    for (int i=0 ; i<length ; i++) {
        if (numbers[i] < 0 || numbers[i] > length -1) {
            return false;
        }
    }
    
    for(int i=0; i<length;i++) {
        while (numbers[i] != i) {
            if (numbers[i] == numbers[numbers[i]]) {
                *duplication = numbers[I];
                return true;
            }
            int temp = numbers[I];
            numbers[i] =  numbers[temp];
            numbers[temp] = temp;
        }
        
        
    }
    
    return false;
}


int main(int argc, const char * argv[]) {
    // insert code here...
//    std::cout << "Hello, World!\n";
    int numbers[] = {3,1,2,0,2,5,3};
    int  dunplication = 0;
    bool res = duplicate(numbers, 7, &dunplication);

    return 0;
}

OC版本

//
//  main.m
//  數(shù)字中重復(fù)數(shù)字
//
//  Created by 張傳奇 on 2018/7/31.
//  Copyright ? 2018年 張傳奇. All rights reserved.
//

#import <Foundation/Foundation.h>

BOOL duplicate(NSMutableArray * numbers,int * duplication) {
    
    if (numbers == nil || numbers.count <1) {
        return NO;
    }
    for (NSNumber * obj in numbers) {
        if (obj.intValue < 0 || obj.intValue > numbers.count-1) {
            return NO;
        }
    }
    
    for (int i=0; i<numbers.count; i++) {
        NSNumber * tempi = numbers[I];
        while (tempi.intValue != i) {
            if ([tempi isEqualToNumber: numbers[tempi.intValue]]) {
                *duplication = tempi.intValue;
                return YES;
            }
            int temp = tempi.intValue;
            [numbers insertObject:numbers[temp] atIndex:i];
            numbers[temp] =[NSNumber numberWithInt:temp];
        }
    }
  
    return NO;
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        // insert code here...
        NSMutableArray * numbers = [NSMutableArray arrayWithObjects:@3,@1,@2,@0,@2,@5,@3, nil];
        int * duplication;
        duplicate(numbers, &duplication);
        NSLog(@"%d",duplication);
    }
    return 0;
}

Tips:吐槽吐槽 oc寫算法實(shí)在太操蛋了，手寫感覺有點(diǎn)涼涼??

題目二：不修改數(shù)組找出重復(fù)的數(shù)字
在一個長度為n+1的數(shù)組里的所有數(shù)字都在1~n的范圍，所有數(shù)組中至少有一個數(shù)字是重復(fù)的。請找出數(shù)組中的任意一個重復(fù)的數(shù)字，但不能修改輸入的數(shù)組。例如，如果輸入長度為8的數(shù)組{2，3，5，4，3，2，6，7}，那么對應(yīng)的輸出是重復(fù)的數(shù)字2或者3。