一道简单的算法题

我们每周有技术分享会，今天有道算法跟大家分享下。

题目

我说说我知道的三种思路

• 先剔除N，再找出最大值

- (void)justTest{
    NSMutableArray *testArr = [NSMutableArray arrayWithArray:@[@[@3,@2,@1,@0],@[@23,@4,@4,@4,@4,@23]]];
    for (int i = 0; i < testArr.count; i++) {
        [self getMax:testArr[i]];
    }
}

- (void)getMax:(NSArray*)arr{
    NSMutableArray *temp = [NSMutableArray arrayWithArray:arr];
    for (int i = 0; i < arr.count; i ++) {
        NSNumber *num = arr[i];
        if (num.integerValue == arr.count - 1) {
            [temp removeObjectAtIndex:i];
            break;
        }
    }
    NSInteger max = 0;
    for (int i = 0; i < temp.count; i ++) {
        NSNumber *num = temp[i];
        if (max < num.integerValue) {
            max = num.integerValue;
        }
    }
    NSLog(@"最大数%ld",max);
}

这种方式要for循环两次。

• 只找出N,再找出最大值

- (void)justTest{
    NSMutableArray *testArr = [NSMutableArray arrayWithArray:@[@[@3,@2,@1,@0],@[@23,@4,@4,@4,@4,@23]]];
    for (int i = 0; i < testArr.count; i++) {
        [self getMax:testArr[i]];
    }
}

- (void)getMax:(NSArray*)arr{
    NSInteger N = 0;
    NSInteger max = 0;
    for (int i = 0; i < arr.count; i ++) {
        NSNumber *num = arr[i];
        if (num.integerValue == arr.count - 1 && N == 0) {
            N = num.integerValue;
        }else{
            if (num.integerValue > max) {
                max = num.integerValue;
            }
        }
    }
    NSLog(@"最大数%ld",max);
}

这种方式只要for循环一次性能更优。

• 通过冒泡排序方式

- (void)justTest{
    NSMutableArray *testArr = [NSMutableArray arrayWithArray:@[@[@3,@2,@1,@0],@[@23,@4,@9,@4,@4,@23]]];
    for (int i = 0; i < testArr.count; i++) {
        [self getMax:testArr[i]];
    }
}

- (void)getMax:(NSArray*)arr{
    NSMutableArray *tempArr = [NSMutableArray arrayWithArray:arr];
    for (int i = 0; i < tempArr.count - 1; i ++) {
        for (int j = 0; j < tempArr.count - 1 - i; j++) {
            if ([tempArr[j] integerValue] > [tempArr[j+1] integerValue]) {
                NSNumber *temp = tempArr[j];
                tempArr[j] = tempArr[j + 1];
                tempArr[j + 1] = temp;
            }
        }
    }
    NSInteger max = [tempArr.lastObject integerValue];
    NSInteger temp;
    if (max != tempArr.count) {
        temp = max;
    }else{
        temp = [tempArr[tempArr.count - 2] integerValue];
    }
    NSLog(@"最大数%ld",temp);
}

这种方式最耗时，遍历次数最多。

知识回顾

• 二分查找(递归和非递归)

//递归查找
int binarySearch2(int a[], int value, int low, int high)
{
    int mid = (low + high)/2;
    if (a[mid] == value) {
        return mid;
    }else if (a[mid] > value){
        return binarySearch2(a, value, low, mid - 1);
    }else{
        return binarySearch2(a, value, mid + 1, high);
    }
}

// 非递归查找
int binarySearch(int a[], int value, int n)
{
    int low, high, mid;
    low = 0;
    high = n - 1;
    mid = (low + high)/2;
    while (low < high) {
        if (a[mid] == value) {
            return mid;
        }else if (a[mid] > value){
            high = mid - 1;
        }else{
            low = mid + 1;
        }
    }
    return -1;
}

• 快速查找

void quicksort(int array[], int maxlen, int begin, int end)
{
    if (begin + 2 > end) {
        return;
    }
    int i = begin + 1;
    int j = end;
    if(begin < end)
    {
        while(i < j)
        {
            if(array[i] > array[begin]){
                int temp = array[i];
                array[i]= array[j];
                array[j]= temp;
                j--;
            }else{
                i++;
            }
        }
        
        if(array[i] >= array[begin]) {
            i--;
        }
        
        int temp = array[begin];
        array[begin] = array[i];
        array[i]= temp;
        
        quicksort(array, maxlen, begin, i);
        quicksort(array, maxlen, j, end);
    }
}