如何统计int数组元素出现次数并排序？无库高效实现方法

Hey there! Let's break down these two integer array problems with efficient, no-third-party-library solutions as you requested. I'll keep things practical and focused on plain loops/conditionals, as specified.

1. Count Occurrences of Specified Integers & Output Sorted Results #

First, let's clarify the problem: I’m assuming you have a target integer array, plus a set of specified integers you want to count. We’ll tally how many times each specified integer appears, then sort those counts and output them. If you meant sorting the original array first before counting, just let me know—I can adjust the solution!

Step-by-Step Implementation #

1. Tally occurrences: Loop through each specified integer, then iterate over the target array to count matches. Store these counts in a temporary list/array.
2. Sort the counts: Implement a basic sorting algorithm (like selection sort) using only loops and conditionals—no built-in sort functions allowed here.

Example Code (Java-like pseudocode)

// Target array we're analyzing
int[] targetArray = {1, 3, 5, 3, 7, 3, 5, 9};
// Integers we need to count occurrences of
int[] specifiedNums = {3, 5, 9};
// Array to store our counts
int[] counts = new int[specifiedNums.length];

// Step 1: Count occurrences for each specified integer
for (int i = 0; i < specifiedNums.length; i++) {
    int currentCount = 0;
    for (int num : targetArray) {
        if (num == specifiedNums[i]) {
            currentCount++;
        }
    }
    counts[i] = currentCount;
}

// Step 2: Sort the counts using selection sort
for (int i = 0; i < counts.length - 1; i++) {
    int minIndex = i;
    for (int j = i + 1; j < counts.length; j++) {
        if (counts[j] < counts[minIndex]) {
            minIndex = j;
        }
    }
    // Swap to place the smallest element at the current index
    int temp = counts[i];
    counts[i] = counts[minIndex];
    counts[minIndex] = temp;
}

// Output the sorted counts
for (int count : counts) {
    System.out.println(count);
}

This will output 1, 2, 3 (since 9 appears once, 5 twice, 3 three times).

Pro tip: If you have a lot of specified integers, sorting the target array first and using binary search to find the first/last occurrence of each specified integer will reduce time complexity from O(m*n) to O(n log n + m log n), where m is the number of specified integers.

2. Count All Unique Integers & Output Sorted by Integer Value (Optimal Efficient Solution) #

This problem asks us to count every unique integer in the array, then output each integer and its count sorted in ascending order of the integer itself. No third-party libraries allowed—just loops and conditionals.

The Efficient Approach #

The key here is to sort the original array first. Once sorted, all duplicates are grouped together, so we can count occurrences in a single pass. Sorting takes O(n log n) time, which is way better than the O(n²) nested-loop approach for finding unique elements without sorting.

Step-by-Step Implementation #

1. Sort the array: Use merge sort (stable, consistent O(n log n) time) or quicksort (faster in practice, O(n log n) average time). We’ll implement merge sort here.
2. Count in one pass: Traverse the sorted array, tracking the current number and its count. When we hit a new number, output the previous number/count and reset the count.
3. Output the final entry: Don’t forget to print the last number and count after the loop ends.

Example Code (Java-like pseudocode)

int[] targetArray = {5, 2, 8, 2, 5, 5, 9, 1};

// Step 1: Sort the array using merge sort
mergeSort(targetArray, 0, targetArray.length - 1);

// Step 2: Count occurrences and output results
if (targetArray.length == 0) {
    return;
}

int currentNum = targetArray[0];
int count = 1;

for (int i = 1; i < targetArray.length; i++) {
    if (targetArray[i] == currentNum) {
        count++;
    } else {
        System.out.println("Number: " + currentNum + ", Count: " + count);
        currentNum = targetArray[i];
        count = 1;
    }
}
// Output the last number and count
System.out.println("Number: " + currentNum + ", Count: " + count);

Merge Sort Implementation (Required for Step 1)

Here’s how to implement merge sort with only loops and conditionals:

void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

void merge(int[] arr, int left, int mid, int right) {
    int leftSize = mid - left + 1;
    int rightSize = right - mid;

    // Temporary arrays to hold split data
    int[] leftArr = new int[leftSize];
    int[] rightArr = new int[rightSize];

    // Copy data to temp arrays
    for (int i = 0; i < leftSize; i++) {
        leftArr[i] = arr[left + i];
    }
    for (int j = 0; j < rightSize; j++) {
        rightArr[j] = arr[mid + 1 + j];
    }

    // Merge temp arrays back into the original array
    int i = 0, j = 0, k = left;
    while (i < leftSize && j < rightSize) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

    // Copy remaining elements from left array
    while (i < leftSize) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }

    // Copy remaining elements from right array
    while (j < rightSize) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}

Why This Is Efficient #

• Sorting: Merge sort runs in O(n log n) time, the best possible for comparison-based sorting.
• Counting: The single pass after sorting is O(n) time, so overall time complexity is O(n log n)—a huge improvement over O(n²) nested loops.
• Space: Merge sort uses O(n) auxiliary space for temporary arrays, which is acceptable for most use cases. If you need in-place sorting, quicksort is a great alternative (just note its worst-case O(n²) time, which is rare in practice).

内容的提问来源于stack exchange，提问作者MSmS