剑指 Offer 40. 最小的 k 个数

1
2
3
4

func getLeastNumbers(arr []int, k int) []int {
    sort.Ints(arr)
    return arr[:k]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

type MaxHeap struct {
    sort.IntSlice
}

func (this *MaxHeap) Less(i, j int) bool {
    return this.IntSlice[i] > this.IntSlice[j]
}

func (this *MaxHeap) Push(v interface{}) {
    this.IntSlice = append(this.IntSlice, v.(int))
}

func (this *MaxHeap) Pop() interface{} {
    ret := this.IntSlice[len(this.IntSlice)-1]
    this.IntSlice = this.IntSlice[:len(this.IntSlice)-1]
    return ret
}

func getLeastNumbers(arr []int, k int) []int {
    if 0 == k {
        return []int{}
    }
    maxHeap := &MaxHeap{}
    for _, val := range arr {
        if len(maxHeap.IntSlice) < k {
            heap.Push(maxHeap, val)
        } else if val < maxHeap.IntSlice[0] {
            heap.Pop(maxHeap)
            heap.Push(maxHeap, val)
        }
    }
    return maxHeap.IntSlice
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

func getLeastNumbers(arr []int, k int) []int {
    if 0 == len(arr) {
        return []int{}
    }

    var quickSort func(l, r, k int)
    rand.New(rand.NewSource(time.Now().UnixNano()))
    quickSort = func(l, r, k int) {
        if l >= r {
            return
        }
        idx := rand.Intn(r-l+1) + l
        arr[l], arr[idx], idx = arr[idx], arr[l], l+1
        for i := l + 1; i <= r; i++ {
            if arr[i] <= arr[l] {
                arr[i], arr[idx] = arr[idx], arr[i]
                idx++
            }
        }
        arr[l], arr[idx-1] = arr[idx-1], arr[l]
        x := idx - l
        if x > k {
            quickSort(l, idx-2, k)
        } else if x < k {
            quickSort(idx, r, k-idx+l)
        }
    }
    quickSort(0, len(arr)-1, k)
    return arr[:k]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Solution {
    int partition(vector<int>& nums, int l, int r) {
        int pivot = nums[r];
        int i = l - 1;
        for (int j = l; j <= r - 1; ++j) {
            if (nums[j] <= pivot) {
                i = i + 1;
                swap(nums[i], nums[j]);
            }
        }
        swap(nums[i + 1], nums[r]);
        return i + 1;
    }

    // 基于随机的划分
    int randomized_partition(vector<int>& nums, int l, int r) {
        int i = rand() % (r - l + 1) + l;
        swap(nums[r], nums[i]);
        return partition(nums, l, r);
    }

    void randomized_selected(vector<int>& arr, int l, int r, int k) {
        if (l >= r) {
            return;
        }
        int pos = randomized_partition(arr, l, r);
        int num = pos - l + 1;
        if (k == num) {
            return;
        } else if (k < num) {
            randomized_selected(arr, l, pos - 1, k);
        } else {
            randomized_selected(arr, pos + 1, r, k - num);
        }
    }

public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        srand((unsigned)time(NULL));
        randomized_selected(arr, 0, (int)arr.size() - 1, k);
        vector<int> vec;
        for (int i = 0; i < k; ++i) {
            vec.push_back(arr[i]);
        }
        return vec;
    }
};