剑指offer-数组中重复的数字

题目一：找出数组中重复的数字
在一个长度为n的数组里所有数字都在0~n-1的范围内，数组中某些数字是重复的，单不知道有几个重复数字，也不知道每个数字重复了几次，请找出数组中任意的数字，例如长度为7的数组{2，3，1，0，2，5，3}，那么对应的重复数字2或者3

因为数字不重复而且在0~n-1内，所以解题精髓就是用数组把内容插入到数组坐标的相应位置，然后比对 如果发现该数字在数组坐标位置相同则代表有重复。

官方demo

//
//  main.cpp
//  数组中找重复
//
//  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
//  数字中重复数字
//
//  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写算法实在太操蛋了，手写感觉有点凉凉😝

题目二：不修改数组找出重复的数字
在一个长度为n+1的数组里的所有数字都在1~n的范围，所有数组中至少有一个数字是重复的。请找出数组中的任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2，3，5，4，3，2，6，7}，那么对应的输出是重复的数字2或者3。