首页 > 代码库 > 常见的算法

常见的算法

/* 快速排序

 * 升序排列

 */

- (void)quickSortArray: (NSArray *)array withLeftIndex: (NSInteger)leftIndex andRightIndex: (NSInteger)rightIndex {

    NSMutableArray *arr = [NSMutableArray arrayWithArray:array];

    if (leftIndex >= rightIndex) {

        return;

    }

    NSInteger i = leftIndex;

    NSInteger j = rightIndex;

    NSInteger key = [arr[leftIndex] integerValue];

    while (i < j) {

        while (i < j && key >= [arr[j] integerValue]) {

            j--;

        }

        arr[i] = arr[j];

        while (i < j && key <= [arr[i] integerValue]) {

            i++;

        }

        arr[j] = arr[i];

    }

    arr[i] = @(key);

    [self quickSortArray:arr withLeftIndex:leftIndex andRightIndex:i - 1];

    [self quickSortArray:arr withLeftIndex:i + 1 andRightIndex:rightIndex];

}

 

/* 冒泡排序

 * 倒序排列 

 * 时间复杂度 O(n^2)

 */

- (NSArray *)sortArrayWithDesc: (NSArray *)array {

    NSMutableArray *arr = [NSMutableArray arrayWithArray:array];

    for (int i = 0; i < arr.count - 1; i++) {

        for (int j = 0; j < arr.count - i - 1; j++) {

            if (arr[j] < arr[j+1]) {

                NSNumber *temp = arr[j];

                arr[j] = arr[j+1];

                arr[j+1] = temp;

            }

        }

    }

    return (NSArray *)arr;

}

 

/* 选择排序

 * 升序排列 

 */

- (NSArray *)sortArrayWithAsc: (NSArray *)array {

    NSMutableArray *arr = [NSMutableArray arrayWithArray:array];

    for (NSInteger i = 0; i < arr.count - 1; i++) {

        NSInteger index = 0;

        index = i;

        for (NSInteger j = i + 1; j < arr.count; j++) {

            if (arr[index] > arr[j]) {

                index = j;

            }

        }

        if (index != i) {

            NSNumber *temp = arr[i];

            arr[i] = arr[index];

            arr[index] = temp;

        }

    }

    return (NSArray *)arr;

}

 

 

/* 从排好序的数组中去重

 * 时间复杂度O(n), 空间复杂度O(1)

 */

- (NSInteger)removeDuplicatesFromSortedArray: (NSArray *)nums {

    if (nums.count <= 0) return 0;

    NSInteger index = 0;

    NSMutableArray *temp = [NSMutableArray arrayWithArray:nums];

    for (NSInteger i = 1; i < temp.count; i++) {

        if (temp[index] != temp[i]) {

            temp[++index] = temp[i];

        }

    }

    NSRange range = NSMakeRange(index, nums.count - index - 1);

    [temp removeObjectsInRange:range];

    NSLog(@"temp===%@", temp);

    return index + 1;

}

 

/* 从排好序的数组中去重,重复最多出现n次

 * 时间复杂度O(n), 空间复杂度O(1)

 */

- (NSInteger)removeDuplicatesFromSortedArray: (NSArray *)nums MostDuplicatesCount: (NSInteger)times {

    if (nums.count <= times) return nums.count;

    NSInteger index = times;

    NSMutableArray *temp = [NSMutableArray arrayWithArray:nums];

    for (NSInteger i = 1; i < temp.count; i++) {

        if (temp[i] != temp[index - times]) {

            temp[index++] = temp[i];

        }

    }

    NSRange range = NSMakeRange(index, nums.count - index);

    [temp removeObjectsInRange:range];

    NSLog(@"temp===%@", temp);

    return index;

}

 

/* 数组无重复,从数组中找到target的位置

 * 时间复杂度O(log n), 空间复杂度O(1)

 */

- (NSInteger)searchInRotatedSortedArray: (NSArray *)nums withTarget: (NSNumber *)target {

    NSInteger first = 0;

    NSInteger last = nums.count;

    while (first != last) {

        NSInteger mid = first + (last - first) / 2 ;

        if (nums[mid] == target) {

            return mid;

        }

        if (nums[first] <= nums[mid]) {

            if (nums[first] <= target && target < nums[mid]) {

                last = mid;

            } else {

                first = mid + 1;

            }

        }

        else {

            if (nums[mid] < target && target <= nums[last-1]) {

                first = mid + 1;

            } else {

                last = mid;

            }

        }

    }

    return -1;

}

 

常见的算法